Submission #125640

#TimeUsernameProblemLanguageResultExecution timeMemory
125640nxteruDreaming (IOI13_dreaming)C++14
18 / 100
66 ms12280 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; #define PB push_back #define F first #define S second #define INF 1000000001 int n,m,dp[100005],l[100005],r[100005]; vector<P>g[100005]; bool vis[100005]; void dfs1(int v,int p){ vis[v]=true; dp[v]=0; for(int i=0;i<g[v].size();i++){ int u=g[v][i].F,c=g[v][i].S; if(u==p)continue; dfs1(u,v); dp[v]=max(dp[v],dp[u]+c); } } int dfs2(int v,int p,int x){ for(int i=0;i<g[v].size();i++)l[i]=0,r[i]=0; for(int i=0;i<g[v].size();i++){ int u=g[v][i].F,c=g[v][i].S; if(u==p){ dp[v]=max(dp[v],x+c); l[i]=x+c,r[i]=x+c; }else l[i]=dp[u]+c,r[i]=dp[u]+c; } int res=dp[v]; for(int i=1;i<g[v].size();i++)l[i]=max(l[i],l[i-1]); for(int i=g[v].size()-1;i>0;i--)r[i-1]=max(r[i-1],r[i]); for(int i=0;i<g[v].size();i++){ int u=g[v][i].F; if(u==p)continue; int c=0; if(i>0)c=max(c,l[i-1]); if(i+1<g[v].size())c=max(c,r[i+1]); res=min(res,dfs2(u,v,c)); } return res; } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { n=N,m=M; for(int i=0;i<m;i++){ g[A[i]].PB(P(B[i],T[i])); g[B[i]].PB(P(A[i],T[i])); } vector<int>p; for(int i=0;i<n;i++){ if(!vis[i]){ dfs1(i,-1); p.PB(dfs2(i,-1,0)); } } sort(p.begin(),p.end(),greater<int>()); for(int i=1;i<p.size();i++)p[i]+=L; p.PB(0); sort(p.begin(),p.end(),greater<int>()); return p[0]+p[1]; }

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
dreaming.cpp: In function 'int dfs2(int, int, int)':
dreaming.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)l[i]=0,r[i]=0;
              ~^~~~~~~~~~~~
dreaming.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
dreaming.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<g[v].size();i++)l[i]=max(l[i],l[i-1]);
              ~^~~~~~~~~~~~
dreaming.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
dreaming.cpp:39:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1<g[v].size())c=max(c,r[i+1]);
      ~~~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<p.size();i++)p[i]+=L;
              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...