Submission #125654

#TimeUsernameProblemLanguageResultExecution timeMemory
125654nxteruDreaming (IOI13_dreaming)C++14
100 / 100
120 ms21896 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],dp2[100005],ans; vector<P>g[100005]; bool vis[100005]; int dfs1(int v,int p){ vis[v]=true; int res=0; dp[v]=0; dp2[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; res=max(res,dfs1(u,v)); int x=dp[u]+c; if(dp[v]<x)swap(x,dp[v]); dp2[v]=max(dp2[v],x); } return max(res,dp[v]+dp2[v]); } int dfs2(int v,int p,int x){ int l[g[v].size()],r[g[v].size()]; 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]){ ans=max(ans,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 max(ans,p[0]+p[1]); }

Compilation message (stderr)

dreaming.cpp: In function 'int dfs1(int, int)':
dreaming.cpp:17: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:29: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:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
dreaming.cpp:38: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:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
dreaming.cpp:45: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:64: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...