Submission #115044

#	Time	Username	Problem	Language	Result	Execution time	Memory
115044		ansol4328	Race (IOI11_race)	C++11	0 / 100	2 ms	384 KiB

race

#include "race.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];
P dist[1000005], from[1000005];
 
void clr_dist(int v, int prev)
{
    dist[v]=P(1e9,1e9);
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        int nxt=lst[v][i].first;
        if(nxt!=prev && !check[nxt]) clr_dist(nxt,v);
    }
}
 
void get_dist(int v, int prev, int dst, int cnt, int root)
{
    if(dist[dst].first>=cnt)
    {
        from[dst].second=from[dst].first;
        dist[dst].second=dist[dst].first;
        from[dst].first=root;
        dist[dst].first=cnt;
    }
    else if(dist[dst].second>cnt) dist[dst].second=cnt;
 
    if(k-dst==dst && from[dst].first==root && from[dst].second==root)
        res=min(res,dist[dst].first+dist[dst].second);
    else if(k-dst!=dst && from[dst].first==root && from[k-dst].first==root)
        res=min(res,dist[dst].first+dist[k-dst].first);
 
    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,root);
        }
    }
}
 
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);
        get_dist(v,-1,0,0,v);
        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;
}

Compilation message (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)':
race.cpp:74: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, int)':
race.cpp:97: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:132:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0 ; i<ctree[v].size() ; i++)
                       ~^~~~~~~~~~~~~~~~

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