oj.uz

Submission #18619

# Submission time Handle Problem Language Result Execution time Memory
18619 2016-02-12T15:45:31 Z ggoh Race (IOI11_race) C++
0 / 100
 3 ms 1528 KB 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
#include<vector>
int a,i,j,x,y,sz2,sz,len[200005],st[200005],z,maxtree[200005],tot[200005],v[200005],t;
int ans,b;
struct A{
    int to,cost;
};
struct B{
    int ho,di;
}data[50005],data2[50005];
bool cmp(B aa,B bb){return aa.di<bb.di;}
std::vector<A>G[50005];
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)
{
    if(dis>b)return ;
    data[sz++]={how,dis};
    data2[sz2++]={how,dis};
    if(dis==b&&(ans==-1||ans>how))
    {
        ans=how;
    }
    v[p]=1;
    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;
    for(int i=0;i<=b;i++)len[b]=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;
    int q;
    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)
                {
                    len[data[j].di]=data[j].ho;
                }
            }
        }
    }
    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

race.cpp: In function 'void dfs(int)':
race.cpp:21: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:43: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:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[u].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<G[u].size();i++)
                 ~^~~~~~~~~~~~
race.cpp:67:9: warning: unused variable 'q' [-Wunused-variable]
     int q;
         ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -