Submission #31788

#TimeUsernameProblemLanguageResultExecution timeMemory
31788DiuvenDreaming (IOI13_dreaming)C++11
100 / 100
205 ms15964 KiB
#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef struct {int to, cost;} edge; vector<edge> G[100010], T(100010); vector<int> rad; bool done[100010]; int N, M, L, tmp, sz[100010], u, D; int find(int v, bool trace=false, int p=-1, int d=0){ done[v]=true; if(tmp<d) tmp=d, u=v; int mx=0; for(auto& e:G[v]){ if(e.to==p) continue; int down=find(e.to, false, v, d+e.cost)+e.cost; if(down>mx) mx=down, T[v]=e; } return mx; } int findcen(int v){ tmp=-1, find(v); int a=u; tmp=-1, T.clear(), find(a,true); int b=u, dia=tmp, now=0; while(a!=b){ int nxt=now+T[a].cost; if(nxt<=dia-nxt){ a=T[a].to, now=nxt; continue; } if(max(now, dia-now)>max(nxt, dia-nxt)) a=T[a].to; break; } return a; } int travelTime(int N, int M, int L, int A[], int B[], int T[]){ for(int 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(int i=1; i<=N; i++) if(!done[i]){ int c=findcen(i); tmp=-1, find(c), rad.push_back(tmp); tmp=-1, find(u), D=max(D, tmp); } sort(rad.begin(), rad.end(), greater<int>()); if(rad.size()>1U) D=max(D, rad[0]+rad[1]+L); if(rad.size()>2U) D=max(D, rad[1]+rad[2]+2*L); return D; }
#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...