# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

96747 | 2019-02-11T17:06:56 Z | figter001 | Dreaming (IOI13_dreaming) | C++14 | 99 ms | 10660 KB |

#include "dreaming.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5; vector<pair<int,int>> g[maxn]; bool idx[maxn]; vector<int> C; int sz[maxn],mx,to,used[maxn],cst[maxn][2],t,best,mn,vis[maxn],c; void path(int u,int cost){ idx[u] = vis[u] = c; if(cost > mx){ mx = cost; to = u; } for(pair<int,int> cur : g[u]){ int v = cur.first; int w = cur.second; if(vis[v] == c)continue; path(v,cost + w); } } void dfs(int u,int cost){ vis[u] = c; cst[u][t] = cost; if(t == 1){ if(max(cst[u][0],cst[u][1]) < mn){ mn = max(cst[u][0],cst[u][1]); best = u; } } for(pair<int,int> cur : g[u]){ int v = cur.first; int w = cur.second; if(vis[v] == c)continue; dfs(v,cost + w); } } void find(int s){ mn = 2e9; mx = 0; c++; path(s,0); t = 0; c++; dfs(to,0); c++; mx = 0; path(to,0); t = 1; c++; dfs(to,0); s = best; C.push_back(s); } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i=0;i<M;i++){ g[A[i]].push_back({B[i],T[i]}); g[B[i]].push_back({A[i],T[i]}); } for(int i=0;i<N;i++) if(!idx[i]) find(i); for(int i=1;i<C.size();i++){ g[C[i]].push_back({C[0],L}); g[C[0]].push_back({C[i],L}); } c++; mx = 0; path(0,0); c++; mx = 0; path(to,0); return mx; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 71 ms | 10616 KB | Output is correct |

2 | Correct | 67 ms | 10660 KB | Output is correct |

3 | Correct | 43 ms | 7928 KB | Output is correct |

4 | Correct | 12 ms | 3948 KB | Output is correct |

5 | Correct | 11 ms | 3328 KB | Output is correct |

6 | Correct | 20 ms | 4352 KB | Output is correct |

7 | Correct | 3 ms | 2688 KB | Output is correct |

8 | Correct | 39 ms | 5624 KB | Output is correct |

9 | Correct | 48 ms | 6776 KB | Output is correct |

10 | Correct | 5 ms | 2816 KB | Output is correct |

11 | Correct | 69 ms | 8184 KB | Output is correct |

12 | Correct | 99 ms | 9464 KB | Output is correct |

13 | Correct | 4 ms | 2816 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 71 ms | 10616 KB | Output is correct |

2 | Correct | 67 ms | 10660 KB | Output is correct |

3 | Correct | 43 ms | 7928 KB | Output is correct |

4 | Correct | 12 ms | 3948 KB | Output is correct |

5 | Correct | 11 ms | 3328 KB | Output is correct |

6 | Correct | 20 ms | 4352 KB | Output is correct |

7 | Correct | 3 ms | 2688 KB | Output is correct |

8 | Correct | 39 ms | 5624 KB | Output is correct |

9 | Correct | 48 ms | 6776 KB | Output is correct |

10 | Correct | 5 ms | 2816 KB | Output is correct |

11 | Correct | 69 ms | 8184 KB | Output is correct |

12 | Correct | 99 ms | 9464 KB | Output is correct |

13 | Correct | 4 ms | 2816 KB | Output is correct |

14 | Correct | 3 ms | 2688 KB | Output is correct |

15 | Correct | 3 ms | 2688 KB | Output is correct |

16 | Correct | 3 ms | 2688 KB | Output is correct |

17 | Correct | 3 ms | 2688 KB | Output is correct |

18 | Correct | 4 ms | 2688 KB | Output is correct |

19 | Correct | 3 ms | 2688 KB | Output is correct |

20 | Correct | 4 ms | 2688 KB | Output is correct |

21 | Correct | 4 ms | 2688 KB | Output is correct |

22 | Correct | 3 ms | 2688 KB | Output is correct |

23 | Correct | 3 ms | 2660 KB | Output is correct |

24 | Correct | 4 ms | 2688 KB | Output is correct |

25 | Correct | 4 ms | 2688 KB | Output is correct |

26 | Correct | 4 ms | 2688 KB | Output is correct |

27 | Correct | 3 ms | 2688 KB | Output is correct |

28 | Incorrect | 3 ms | 2688 KB | Output isn't correct |

29 | Halted | 0 ms | 0 KB | - |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 71 ms | 10616 KB | Output is correct |

2 | Correct | 67 ms | 10660 KB | Output is correct |

3 | Correct | 43 ms | 7928 KB | Output is correct |

4 | Correct | 12 ms | 3948 KB | Output is correct |

5 | Correct | 11 ms | 3328 KB | Output is correct |

6 | Correct | 20 ms | 4352 KB | Output is correct |

7 | Correct | 3 ms | 2688 KB | Output is correct |

8 | Correct | 39 ms | 5624 KB | Output is correct |

9 | Correct | 48 ms | 6776 KB | Output is correct |

10 | Correct | 5 ms | 2816 KB | Output is correct |

11 | Correct | 69 ms | 8184 KB | Output is correct |

12 | Correct | 99 ms | 9464 KB | Output is correct |

13 | Correct | 4 ms | 2816 KB | Output is correct |

14 | Correct | 3 ms | 2688 KB | Output is correct |

15 | Correct | 3 ms | 2688 KB | Output is correct |

16 | Correct | 3 ms | 2688 KB | Output is correct |

17 | Correct | 3 ms | 2688 KB | Output is correct |

18 | Correct | 4 ms | 2688 KB | Output is correct |

19 | Correct | 3 ms | 2688 KB | Output is correct |

20 | Correct | 4 ms | 2688 KB | Output is correct |

21 | Correct | 4 ms | 2688 KB | Output is correct |

22 | Correct | 3 ms | 2688 KB | Output is correct |

23 | Correct | 3 ms | 2660 KB | Output is correct |

24 | Correct | 4 ms | 2688 KB | Output is correct |

25 | Correct | 4 ms | 2688 KB | Output is correct |

26 | Correct | 4 ms | 2688 KB | Output is correct |

27 | Correct | 3 ms | 2688 KB | Output is correct |

28 | Incorrect | 3 ms | 2688 KB | Output isn't correct |

29 | Halted | 0 ms | 0 KB | - |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Incorrect | 35 ms | 7408 KB | Output isn't correct |

2 | Halted | 0 ms | 0 KB | - |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 71 ms | 10616 KB | Output is correct |

2 | Correct | 67 ms | 10660 KB | Output is correct |

3 | Correct | 43 ms | 7928 KB | Output is correct |

4 | Correct | 12 ms | 3948 KB | Output is correct |

5 | Correct | 11 ms | 3328 KB | Output is correct |

6 | Correct | 20 ms | 4352 KB | Output is correct |

7 | Correct | 3 ms | 2688 KB | Output is correct |

8 | Correct | 39 ms | 5624 KB | Output is correct |

9 | Correct | 48 ms | 6776 KB | Output is correct |

10 | Correct | 5 ms | 2816 KB | Output is correct |

11 | Correct | 69 ms | 8184 KB | Output is correct |

12 | Correct | 99 ms | 9464 KB | Output is correct |

13 | Correct | 4 ms | 2816 KB | Output is correct |

14 | Correct | 4 ms | 2732 KB | Output is correct |

15 | Correct | 5 ms | 2844 KB | Output is correct |

16 | Correct | 5 ms | 2916 KB | Output is correct |

17 | Incorrect | 4 ms | 2816 KB | Output isn't correct |

18 | Halted | 0 ms | 0 KB | - |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 71 ms | 10616 KB | Output is correct |

2 | Correct | 67 ms | 10660 KB | Output is correct |

3 | Correct | 43 ms | 7928 KB | Output is correct |

4 | Correct | 12 ms | 3948 KB | Output is correct |

5 | Correct | 11 ms | 3328 KB | Output is correct |

6 | Correct | 20 ms | 4352 KB | Output is correct |

7 | Correct | 3 ms | 2688 KB | Output is correct |

8 | Correct | 39 ms | 5624 KB | Output is correct |

9 | Correct | 48 ms | 6776 KB | Output is correct |

10 | Correct | 5 ms | 2816 KB | Output is correct |

11 | Correct | 69 ms | 8184 KB | Output is correct |

12 | Correct | 99 ms | 9464 KB | Output is correct |

13 | Correct | 4 ms | 2816 KB | Output is correct |

14 | Correct | 3 ms | 2688 KB | Output is correct |

15 | Correct | 3 ms | 2688 KB | Output is correct |

16 | Correct | 3 ms | 2688 KB | Output is correct |

17 | Correct | 3 ms | 2688 KB | Output is correct |

18 | Correct | 4 ms | 2688 KB | Output is correct |

19 | Correct | 3 ms | 2688 KB | Output is correct |

20 | Correct | 4 ms | 2688 KB | Output is correct |

21 | Correct | 4 ms | 2688 KB | Output is correct |

22 | Correct | 3 ms | 2688 KB | Output is correct |

23 | Correct | 3 ms | 2660 KB | Output is correct |

24 | Correct | 4 ms | 2688 KB | Output is correct |

25 | Correct | 4 ms | 2688 KB | Output is correct |

26 | Correct | 4 ms | 2688 KB | Output is correct |

27 | Correct | 3 ms | 2688 KB | Output is correct |

28 | Incorrect | 3 ms | 2688 KB | Output isn't correct |

29 | Halted | 0 ms | 0 KB | - |