Submission #223623

#TimeUsernameProblemLanguageResultExecution timeMemory
223623a_playerDreaming (IOI13_dreaming)C++14
100 / 100
94 ms17544 KiB
#include <bits/stdc++.h> #include "dreaming.h" #define f first #define s second using namespace std; const int nax=1e5+5; struct node{ int a,b,p; }; vector<pair<int,int> > grafo[nax]; node dp[nax]; bitset<nax> v; int mini=INT_MAX; int diam=0; node max3(node a, int b, int pos){ if(b>=a.a)return {b,a.a,pos}; if(b>a.b) return {a.a,b,a.p}; return a; } int dfsb(int n, int a){ v[n]=1; for(auto x:grafo[n]){ if(x.f==a)continue; dp[n]=max3(dp[n],dfsb(x.f,n)+x.s,x.f); } diam=max(diam,dp[n].a+dp[n].b); return dp[n].a; } void dfst(int n, int a, int d){ mini=min(mini,max(d,dp[n].a)); for(auto x:grafo[n]){ if(x.f==a)continue; int dd=max(d,(x.f!=dp[n].p?dp[n].a:dp[n].b))+x.s; dfst(x.f,n,dd); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]){ for(int i=0;i<M;i++){ grafo[A[i]].push_back({B[i],T[i]}); grafo[B[i]].push_back({A[i],T[i]}); } vector<int> maxes; for(int i=0;i<N;i++){ if(!v[i]){ mini=INT_MAX; dfsb(i,-1); dfst(i,-1,0); maxes.push_back(mini); } } sort(maxes.begin(),maxes.end(),greater<int>()); int ans=diam; if(maxes.size()>1)ans=max(ans,maxes[0]+maxes[1]+L); if(maxes.size()>2)ans=max(ans,maxes[1]+maxes[2]+2*L); return ans; }
#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...