# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
14796 | 2015-06-26T04:38:34 Z | progressive | Dreaming (IOI13_dreaming) | C++ | 60 ms | 15092 KB |
#include "dreaming.h" #include <vector> #include <algorithm> using namespace std; static const int MAXN=100100; vector<pair<int,int> > conn[MAXN]; static int color[MAXN]; static int tp=0; static int hdist[MAXN]; static int dist[MAXN]; static int parent[MAXN]; vector<int> samecolor[MAXN]; vector<int> radius; void colordfs(int a,int pa,int c) { color[a]=c; samecolor[c].push_back(a); for(int i=0;i<conn[a].size();i++) { int target=conn[a][i].first; if(target==pa) continue; hdist[target]=hdist[a]+conn[a][i].second; colordfs(target,a,c); } } void dfs(int a,int pa) { parent[a]=pa; for(int i=0;i<conn[a].size();i++) { int target=conn[a][i].first; if(target==pa) continue; dist[target]=dist[a]+conn[a][i].second; dfs(target,a); } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i=0;i<M;i++) { conn[A[i]].push_back(make_pair(B[i],T[i])); conn[B[i]].push_back(make_pair(A[i],T[i])); } for(int i=0;i<N;i++) if(!color[i]) colordfs(i,-1,++tp); for(int i=1;i<=tp;i++) { int furthest=samecolor[i][0]; for(int j=1;j<samecolor[i].size();j++) if(hdist[furthest]<hdist[samecolor[i][j]]) furthest=samecolor[i][j]; dfs(furthest,-1); int dia=furthest; for(int j=0;j<samecolor[i].size();j++) if(dist[dia]<dist[samecolor[i][j]]) dia=samecolor[i][j]; int radii=dist[dia]; int res=dist[dia]; int getr=dia; while(~dia) { res=min(res,max(radii-dist[dia],dist[dia])); dia=parent[dia]; } radius.push_back(res); } sort(radius.begin(),radius.end()); reverse(radius.begin(),radius.end()); if(tp==1) return radius[0]; if(tp==2) return radius[0]+radius[1]+L; return max(radius[0]+radius[1]+L,radius[1]+radius[2]+2*L); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 15092 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 15092 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 15092 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 55 ms | 11092 KB | Output is correct |
2 | Correct | 52 ms | 11128 KB | Output is correct |
3 | Correct | 55 ms | 11256 KB | Output is correct |
4 | Correct | 53 ms | 11128 KB | Output is correct |
5 | Correct | 42 ms | 11128 KB | Output is correct |
6 | Correct | 50 ms | 11736 KB | Output is correct |
7 | Correct | 46 ms | 11380 KB | Output is correct |
8 | Correct | 58 ms | 11124 KB | Output is correct |
9 | Correct | 37 ms | 11000 KB | Output is correct |
10 | Correct | 43 ms | 11384 KB | Output is correct |
11 | Correct | 5 ms | 5120 KB | Output is correct |
12 | Correct | 17 ms | 10108 KB | Output is correct |
13 | Correct | 18 ms | 10240 KB | Output is correct |
14 | Correct | 17 ms | 10112 KB | Output is correct |
15 | Correct | 17 ms | 10284 KB | Output is correct |
16 | Correct | 17 ms | 10112 KB | Output is correct |
17 | Correct | 16 ms | 9728 KB | Output is correct |
18 | Correct | 21 ms | 10232 KB | Output is correct |
19 | Correct | 17 ms | 10240 KB | Output is correct |
20 | Correct | 6 ms | 4992 KB | Output is correct |
21 | Correct | 6 ms | 4992 KB | Output is correct |
22 | Correct | 6 ms | 5248 KB | Output is correct |
23 | Correct | 17 ms | 10112 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 15092 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 60 ms | 15092 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |