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

96749 | 2019-02-11T17:23:23 Z | figter001 | Dreaming (IOI13_dreaming) | C++14 | 158 ms | 11044 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]; vector<int> C; int mx,to,cst[maxn],t,best,mn,vis[maxn],c; void path(int u,int cost){ 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; if(t == 1){ cst[u] = max(cst[u],cost); if(cst[u] < mn){ mn = cst[u]; best = u; } }else cst[u] = cost; 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 = -1; c++; path(s,0); int a = to; c++; mx = -1; path(a,0); int b = to; t = 0; c++; dfs(a,0); t = 1; c++; dfs(b,0); C.push_back(best); } 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(!vis[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 = -1; path(0,0); c++; mx = -1; path(to,0); return mx; }

### Compilation message

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

1 | Correct | 63 ms | 10104 KB | Output is correct |

2 | Correct | 80 ms | 10104 KB | Output is correct |

3 | Correct | 45 ms | 7672 KB | Output is correct |

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

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

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

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

8 | Correct | 38 ms | 5496 KB | Output is correct |

9 | Correct | 51 ms | 6520 KB | Output is correct |

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

11 | Correct | 82 ms | 7912 KB | Output is correct |

12 | Correct | 82 ms | 8932 KB | Output is correct |

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

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

1 | Correct | 63 ms | 10104 KB | Output is correct |

2 | Correct | 80 ms | 10104 KB | Output is correct |

3 | Correct | 45 ms | 7672 KB | Output is correct |

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

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

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

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

8 | Correct | 38 ms | 5496 KB | Output is correct |

9 | Correct | 51 ms | 6520 KB | Output is correct |

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

11 | Correct | 82 ms | 7912 KB | Output is correct |

12 | Correct | 82 ms | 8932 KB | Output is correct |

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

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

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

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

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

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

19 | Correct | 4 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 | 2688 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 | Correct | 4 ms | 2688 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

1 | Correct | 63 ms | 10104 KB | Output is correct |

2 | Correct | 80 ms | 10104 KB | Output is correct |

3 | Correct | 45 ms | 7672 KB | Output is correct |

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

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

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

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

8 | Correct | 38 ms | 5496 KB | Output is correct |

9 | Correct | 51 ms | 6520 KB | Output is correct |

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

11 | Correct | 82 ms | 7912 KB | Output is correct |

12 | Correct | 82 ms | 8932 KB | Output is correct |

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

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

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

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

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

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

19 | Correct | 4 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 | 2688 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 | Correct | 4 ms | 2688 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

39 | Correct | 63 ms | 10108 KB | Output is correct |

40 | Correct | 62 ms | 10104 KB | Output is correct |

41 | Correct | 43 ms | 7552 KB | Output is correct |

42 | Correct | 13 ms | 3840 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57 | Correct | 101 ms | 8640 KB | Output is correct |

58 | Correct | 84 ms | 8696 KB | Output is correct |

59 | Correct | 96 ms | 8568 KB | Output is correct |

60 | Correct | 92 ms | 8568 KB | Output is correct |

61 | Correct | 88 ms | 8440 KB | Output is correct |

62 | Correct | 93 ms | 8444 KB | Output is correct |

63 | Correct | 82 ms | 8300 KB | Output is correct |

64 | Correct | 84 ms | 8312 KB | Output is correct |

65 | Correct | 94 ms | 8340 KB | Output is correct |

66 | Correct | 79 ms | 8312 KB | Output is correct |

67 | Correct | 112 ms | 8568 KB | Output is correct |

68 | Correct | 101 ms | 8440 KB | Output is correct |

69 | Correct | 106 ms | 8568 KB | Output is correct |

70 | Correct | 106 ms | 8568 KB | Output is correct |

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

72 | Correct | 6 ms | 2816 KB | Output is correct |

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

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

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

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

77 | Correct | 5 ms | 2944 KB | Output is correct |

78 | Correct | 6 ms | 2944 KB | Output is correct |

79 | Correct | 6 ms | 2816 KB | Output is correct |

80 | Correct | 92 ms | 8440 KB | Output is correct |

81 | Correct | 118 ms | 8528 KB | Output is correct |

82 | Correct | 102 ms | 8440 KB | Output is correct |

83 | Correct | 101 ms | 8440 KB | Output is correct |

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

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

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

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

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

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

90 | Correct | 6 ms | 2816 KB | Output is correct |

91 | Correct | 5 ms | 2944 KB | Output is correct |

92 | Correct | 5 ms | 2944 KB | Output is correct |

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

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

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

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

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

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

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

100 | Correct | 5 ms | 2688 KB | Output is correct |

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

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

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

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

105 | Correct | 20 ms | 4344 KB | Output is correct |

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

107 | Correct | 37 ms | 5496 KB | Output is correct |

108 | Correct | 46 ms | 6528 KB | Output is correct |

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

110 | Correct | 65 ms | 7800 KB | Output is correct |

111 | Correct | 79 ms | 8824 KB | Output is correct |

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

113 | Correct | 158 ms | 11044 KB | Output is correct |

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

1 | Incorrect | 39 ms | 7416 KB | Output isn't correct |

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

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

1 | Correct | 63 ms | 10104 KB | Output is correct |

2 | Correct | 80 ms | 10104 KB | Output is correct |

3 | Correct | 45 ms | 7672 KB | Output is correct |

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

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

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

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

8 | Correct | 38 ms | 5496 KB | Output is correct |

9 | Correct | 51 ms | 6520 KB | Output is correct |

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

11 | Correct | 82 ms | 7912 KB | Output is correct |

12 | Correct | 82 ms | 8932 KB | Output is correct |

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

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

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

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

17 | Incorrect | 5 ms | 2688 KB | Output isn't correct |

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

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

1 | Correct | 63 ms | 10104 KB | Output is correct |

2 | Correct | 80 ms | 10104 KB | Output is correct |

3 | Correct | 45 ms | 7672 KB | Output is correct |

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

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

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

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

8 | Correct | 38 ms | 5496 KB | Output is correct |

9 | Correct | 51 ms | 6520 KB | Output is correct |

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

11 | Correct | 82 ms | 7912 KB | Output is correct |

12 | Correct | 82 ms | 8932 KB | Output is correct |

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

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

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

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

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

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

19 | Correct | 4 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 | 2688 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 | Correct | 4 ms | 2688 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

39 | Correct | 63 ms | 10108 KB | Output is correct |

40 | Correct | 62 ms | 10104 KB | Output is correct |

41 | Correct | 43 ms | 7552 KB | Output is correct |

42 | Correct | 13 ms | 3840 KB | Output is correct |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57 | Correct | 101 ms | 8640 KB | Output is correct |

58 | Correct | 84 ms | 8696 KB | Output is correct |

59 | Correct | 96 ms | 8568 KB | Output is correct |

60 | Correct | 92 ms | 8568 KB | Output is correct |

61 | Correct | 88 ms | 8440 KB | Output is correct |

62 | Correct | 93 ms | 8444 KB | Output is correct |

63 | Correct | 82 ms | 8300 KB | Output is correct |

64 | Correct | 84 ms | 8312 KB | Output is correct |

65 | Correct | 94 ms | 8340 KB | Output is correct |

66 | Correct | 79 ms | 8312 KB | Output is correct |

67 | Correct | 112 ms | 8568 KB | Output is correct |

68 | Correct | 101 ms | 8440 KB | Output is correct |

69 | Correct | 106 ms | 8568 KB | Output is correct |

70 | Correct | 106 ms | 8568 KB | Output is correct |

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

72 | Correct | 6 ms | 2816 KB | Output is correct |

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

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

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

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

77 | Correct | 5 ms | 2944 KB | Output is correct |

78 | Correct | 6 ms | 2944 KB | Output is correct |

79 | Correct | 6 ms | 2816 KB | Output is correct |

80 | Correct | 92 ms | 8440 KB | Output is correct |

81 | Correct | 118 ms | 8528 KB | Output is correct |

82 | Correct | 102 ms | 8440 KB | Output is correct |

83 | Correct | 101 ms | 8440 KB | Output is correct |

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

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

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

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

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

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

90 | Correct | 6 ms | 2816 KB | Output is correct |

91 | Correct | 5 ms | 2944 KB | Output is correct |

92 | Correct | 5 ms | 2944 KB | Output is correct |

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

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

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

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

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

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

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

100 | Correct | 5 ms | 2688 KB | Output is correct |

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

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

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

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

105 | Correct | 20 ms | 4344 KB | Output is correct |

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

107 | Correct | 37 ms | 5496 KB | Output is correct |

108 | Correct | 46 ms | 6528 KB | Output is correct |

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

110 | Correct | 65 ms | 7800 KB | Output is correct |

111 | Correct | 79 ms | 8824 KB | Output is correct |

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

113 | Correct | 158 ms | 11044 KB | Output is correct |

114 | Incorrect | 39 ms | 7416 KB | Output isn't correct |

115 | Halted | 0 ms | 0 KB | - |