Submission #18622

#	Time	Username	Problem	Language	Result	Execution time	Memory
18622		ggoh	Race (IOI11_race)	C++98	100 / 100	603 ms	29820 KiB

race

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
int a,i,j,x,y,sz2,st2[200005],sz,len[1000005],st[200005],z,maxtree[200005],tot[200005],v[200005],t;
int ans,b;
struct A{
    int to,cost;
};
struct B{
    int ho,di;
}data[200005];
std::vector<A>G[200005];
void dfs(int p)
{
    tot[p]=1;
    v[p]=1;
    maxtree[p]=0;
    for(int k=0;k<G[p].size();k++)
    {
        if(v[G[p][k].to]==0)
        {
            dfs(G[p][k].to);
            tot[p]+=tot[G[p][k].to];
            maxtree[p]=std::max(maxtree[p],tot[G[p][k].to]);
        }
    }
    st[t++]=p;
}

void dfs2(int p,int how,int dis)
{
    v[p]=1;
    if(dis>b)return ;
    data[sz++]={how,dis};
    if(dis==b&&(ans==-1||ans>how))
    {
        ans=how;
    }
    for(int k=0;k<G[p].size();k++)
    {
        if(v[G[p][k].to]==0)
        {
            dfs2(G[p][k].to,how+1,dis+G[p][k].cost);
        }
    }
}
void f(int p)
{
    int u=0;
    t=0;
    dfs(p);
    for(int i=0;i<t;i++)
    {
        if(std::max(maxtree[st[i]],tot[p]-tot[st[i]])<=tot[p]/2)
        {
            u=st[i];
        }
        v[st[i]]=0;
    }
    v[u]=1;
    sz2=0;
    for(int i=0;i<G[u].size();i++)
    {
        if(v[G[u][i].to]==0)
        {
            sz=0;
            dfs2(G[u][i].to,1,G[u][i].cost);
            for(int j=0;j<sz;j++)
            {
                if(len[b-data[j].di]&&(ans==-1||len[b-data[j].di]+data[j].ho<ans))
                {
                    ans=len[b-data[j].di]+data[j].ho;
                }
            }
            for(int j=0;j<sz;j++)
            {
                if(len[data[j].di]==0||len[data[j].di]>data[j].ho)
                {
                    if(len[data[j].di]==0)st2[sz2++]=data[j].di;
                    len[data[j].di]=data[j].ho;
                }
            }
        }
    }
    for(int i=0;i<sz2;i++)len[st2[i]]=0;
    for(int i=0;i<t;i++)v[st[i]]=0;
    v[u]=1;
    for(int i=0;i<G[u].size();i++)
    {
        if(v[G[u][i].to]==0)f(G[u][i].to);
    }
}
int best_path(int N,int K,int H[][2],int L[])
{
    a=N;
    b=K;
    for(i=0;i<a-1;i++)
    {
        x=H[i][0]+1;
        y=H[i][1]+1;
        z=L[i];
        G[x].push_back({y,z});
        G[y].push_back({x,z});
    }
    ans=-1;
    f(1);
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int)':
race.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<G[p].size();k++)
                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfs2(int, int, int)':
race.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=0;k<G[p].size();k++)
                 ~^~~~~~~~~~~~
race.cpp: In function 'void f(int)':
race.cpp:64:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[u].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:90:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[u].size();i++)
                 ~^~~~~~~~~~~~

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