제출 #115055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
115055		ansol4328	경주 (Race) (IOI11_race)	C++11	100 / 100	1056 ms	46480 KiB

race

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
typedef pair<int,int> P;
typedef vector<vector<P>> graph;

struct CentroidDecomposition
{
    graph CentTree;
    vector<bool> visit;
    vector<int> sub; // size of subtree
    int tot;
    CentroidDecomposition(int N)
    {
        CentTree.resize(N+5);
        visit.resize(N+5);
        sub.resize(N+5);
    }
    void get_sz(int cur, int prev, graph &tree)
    {
        sub[cur]=1;
        for(int i=0 ; i<tree[cur].size() ; i++)
        {
            int nxt=tree[cur][i].first;
            if(!visit[nxt] && nxt!=prev)
            {
                get_sz(nxt,cur,tree);
                sub[cur]+=sub[nxt];
            }
        }
    }
    int get_cen(int cur, int prev, graph &tree)
    {
        for(int i=0 ; i<tree[cur].size() ; i++)
        {
            int nxt=tree[cur][i].first;
            if(!visit[nxt] && nxt!=prev && sub[nxt]>tot/2)
                return get_cen(nxt,cur,tree);
        }
        return cur;
    }
    int decomp(int cur, int prev, graph &tree)
    {
        get_sz(cur,prev,tree);
        tot=sub[cur];
        int cen=get_cen(cur,prev,tree);
        visit[cen]=true;
        for(int i=0 ; i<tree[cen].size() ; i++)
        {
            int nxt=tree[cen][i].first;
            int nxtcen;
            if(!visit[nxt] && nxt!=prev)
            {
                nxtcen=decomp(nxt,cen,tree);
                CentTree[cen].push_back(P(nxtcen,0));
                CentTree[nxtcen].push_back(P(cen,0));
            }
        }
        return cen;
    }
};

int n, k, res=1e9;
graph lst;
bool check[200005];
int dist[1000005], idx;
P que[200005];

void clr_dist(int v, int prev, int dst)
{
    dist[dst]=1e9;
    dist[k-dst]=1e9;
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        int nxt=lst[v][i].first;
        int d=lst[v][i].second;
        if(nxt!=prev && !check[nxt] && dst+d<=k) clr_dist(nxt,v,dst+d);
    }
}

void get_dist(int v, int prev, int dst, int cnt)
{
    que[++idx]=P(dst,cnt);
    res=min(res,dist[k-dst]+cnt);
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        int nxt=lst[v][i].first;
        int d=lst[v][i].second;
        if(nxt!=prev && !check[nxt] && dst+d<=k)
        {
            get_dist(nxt,v,dst+d,cnt+1);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N, k=K;
    lst.resize(n+5);
    for(int i=0 ; i<n-1 ; i++)
    {
        int x=H[i][0], y=H[i][1], d=L[i];
        x++, y++;
        lst[x].push_back(P(y,d));
        lst[y].push_back(P(x,d));
    }
    CentroidDecomposition T(n);

    int root=T.decomp(1,-1,lst);
    graph &ctree=T.CentTree;
    queue<int> Q;
    Q.push(root);
    check[root]=true;
    while(!Q.empty())
    {
        int v=Q.front();
        Q.pop();
        clr_dist(v,-1,0);
        dist[0]=0;
        for(int i=0 ; i<lst[v].size() ; i++)
        {
            idx=0;
            int nxt=lst[v][i].first;
            int d=lst[v][i].second;
            if(!check[nxt] && d<=k) get_dist(nxt,v,d,1);
            for(int j=1 ; j<=idx ; j++) dist[que[j].first]=min(dist[que[j].first],que[j].second);
        }
        for(int i=0 ; i<ctree[v].size() ; i++)
        {
            int nxt=ctree[v][i].first;
            if(!check[nxt])
            {
                Q.push(nxt);
                check[nxt]=true;
            }
        }
    }
    if(res==1e9) res=-1;
    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In member function 'void CentroidDecomposition::get_sz(int, int, graph&)':
race.cpp:25:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<tree[cur].size() ; i++)
                       ~^~~~~~~~~~~~~~~~~
race.cpp: In member function 'int CentroidDecomposition::get_cen(int, int, graph&)':
race.cpp:37:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<tree[cur].size() ; i++)
                       ~^~~~~~~~~~~~~~~~~
race.cpp: In member function 'int CentroidDecomposition::decomp(int, int, graph&)':
race.cpp:51:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<tree[cen].size() ; i++)
                       ~^~~~~~~~~~~~~~~~~
race.cpp: In function 'void clr_dist(int, int, int)':
race.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[v].size() ; i++)
                   ~^~~~~~~~~~~~~~
race.cpp: In function 'void get_dist(int, int, int, int)':
race.cpp:88:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[v].size() ; i++)
                   ~^~~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:123:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<lst[v].size() ; i++)
                       ~^~~~~~~~~~~~~~
race.cpp:131:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<ctree[v].size() ; i++)
                       ~^~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57