특정한 문제들에서 vector의 정적배열 했을때는 맞았습니다가 나오고 

resize로 동적으로 배열하면 시간초과가 납니다. 혹시 둘의 시간차이가 있나요?

yukariko   3달 전

제 생각엔 코드 전체를 봐야 분석이 가능할것같습니다.

위의 소스는 안되고 아래 소스는 돼요.

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <cstdio>

#include <vector>

#include <queue>

#include <algorithm>

#include <functional>

#include <cstring>

using namespace std;

vector <  vector < pair < int , int > > > v;

bool visit[100004];

int cnt[100004];

int Max=0;

int vertex=0;

void bfs(int V){

    memset(cnt,0,sizeof(cnt));

    memset(visit,false,sizeof(visit));

    queue < int > que;

    que.push(V);

    visit[V]=true;

    while(!que.empty()){

        int x=que.front();

        que.pop();

        for(int i=0; i<(int)v[x].size();i++){

            if(visit[v[x][i].first]!=true){

                cnt[v[x][i].first]=(cnt[x]+v[x][i].second);

                que.push(v[x][i].first);

                visit[v[x][i].first]=true;

                if(Max<cnt[v[x][i].first]){

                    vertex=v[x][i].first;

                    Max=cnt[v[x][i].first];

                }

            }

        }

    }

}

int main(){

    int n;

    scanf("%d",&n);

    for(int i=0; i<n; i++){

        int V;

        int a,length;

        scanf("%d",&V);

        v.resize(V+1);

        while(1){

            scanf("%d",&a);

            if(a==-1){

                break;

            }

            scanf("%d",&length);

            v[V].push_back(make_pair(a,length));

        }

    }


    bfs(1);

    Max=0;


    bfs(vertex);

      printf("%d\n",Max);

}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include <cstdio>

#include <vector>

#include <queue>

#include <algorithm>

#include <functional>

#include <cstring>

using namespace std;

vector   < pair < int , int > > v[100004];

bool visit[100004];

int cnt[100004];

int Max=0;

int vertex=0;

void bfs(int V){

    memset(cnt,0,sizeof(cnt));

    memset(visit,false,sizeof(visit));

    queue < int > que;

    que.push(V);

    visit[V]=true;

    while(!que.empty()){

        int x=que.front();

        que.pop();

        for(int i=0; i<(int)v[x].size();i++){

            if(visit[v[x][i].first]!=true){

                cnt[v[x][i].first]=(cnt[x]+v[x][i].second);

                que.push(v[x][i].first);

                visit[v[x][i].first]=true;

                if(Max<cnt[v[x][i].first]){

                    vertex=v[x][i].first;

                    Max=cnt[v[x][i].first];

                }

            }

        }

    }

}

int main(){

    int n;

    scanf("%d",&n);

    for(int i=0; i<n; i++){

        int V;

        int a,length;

        scanf("%d",&V);

        while(1){

            scanf("%d",&a);

            if(a==-1){

                break;

            }

            scanf("%d",&length);

            v[V].push_back(make_pair(a,length));

        }

    }

    bfs(1);

    Max=0;

    bfs(vertex);

    printf("%d\n",Max);

}


트리의 지름 1167 문제입니다.

kesakiyo   3달 전

resize는요 기존 백터의 크기를 바꾸는거지 안에 내용까지 전부 초기화 시켜주진 않아요.

resize대신 assign을 사용하면 될거에요.

댓글을 작성하려면 로그인해야 합니다.