Submission #15889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15889	2015-08-01T06:32:13 Z	ggoh	Dreaming (IOI13_dreaming)	C++	Compilation error	0 ms	0 KB

dreaming

#include "dreaming.h"
#include<cstdio>
#include<vector>
#include<algorithm>
struct AA{
    int to,cost;
};
std::vector<AA>G[100002];
int ans,i,m,t,st[100002],dis[100002],pos,len,K;
bool v[2][100002];
void dfs(int x,int p)
{
    for(int j=0;j<G[x].size();j++)
    {
        AA u=G[x][j];
        if(!v[p][u.to])
        {
        	dis[u.to]=dis[x]+u.cost;
            if(m<=dis[u.to])
            {
                pos=u.to;m=dis[u.to];
            }
            v[p][u.to]=1;
            dfs(u.to);
        }
    }
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    for(i=0;i<M;i++)
    {
        G[A[i]+1].push_back({B[i]+1,T[i]});
        G[B[i]+1].push_back({A[i]+1,T[i]});
    }
    for(i=1;i<=N;i++)
    {
        if(!v[0][i])
        {
            v[0][i]=1;
            m=0;pos=i;dis[i]=0;
            dfs(i,0);
            m=0;v[1][pos]=1;dis[pos]=0;
            dfs2(pos,1);
            len=std::max(len,m);
            K=m;st[t]=m;
            while(dis[pos])
            {
                for(int k=0;k<G[pos].size();k++)
                {
                    if(dis[G[pos][k].to]+G[pos][k].cost==dis[pos])
                    {
                        K-=G[pos][k].cost;
                        pos=G[pos][k].to;
                        break;
                    }
                }
                st[t]=std::min(st[t],std::max(K,m-K));
            }
            t++;
        }
    }
    std::sort(st,st+t);
    ans=len;
    if(t>1)ans=std::max(st[t-1]+st[t-2]+L,ans);
    if(t>2)ans=std::max(ans,st[t-2]+2*L+st[t-3]);
    return ans;
}

Compilation message

dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<G[x].size();j++)
                 ~^~~~~~~~~~~~
dreaming.cpp:24:21: error: too few arguments to function 'void dfs(int, int)'
             dfs(u.to);
                     ^
dreaming.cpp:11:6: note: declared here
 void dfs(int x,int p)
      ^~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:43:13: error: 'dfs2' was not declared in this scope
             dfs2(pos,1);
             ^~~~
dreaming.cpp:43:13: note: suggested alternative: 'dfs'
             dfs2(pos,1);
             ^~~~
             dfs
dreaming.cpp:48:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k=0;k<G[pos].size();k++)
                             ~^~~~~~~~~~~~~~