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

111787 | 2019-05-16T07:24:57 Z | Mercenary | Race (IOI11_race) | C++14 | 667 ms | 74836 KB |

#include "race.h" #include<bits/stdc++.h> using namespace std; #define taskname "TEST" #define pb push_back typedef long double ld; typedef long long ll; const int maxn = 2e5 + 5; typedef pair<int,int> tpair; int n , sz[maxn] , h[maxn] , k; int res = maxn; vector<tpair> v[maxn]; unordered_map<ll,int> *vec[maxn]; ll dep[maxn]; void DFS1(int u , int p) { sz[u] = 1; for(tpair c : v[u]) { if(p == c.first)continue; h[c.first] = h[u] + 1; dep[c.first] = dep[u] + c.second; DFS1(c.first,u); sz[u] += sz[c.first]; } } void add(unordered_map<ll,int> & s , int h1 , ll d1 , int& h , ll& d , int type) { if(type == 1) { ll need = k - d1 + 2 * d; if(!s.count(need))return; res = min(res ,s[need] + h1 - 2 * h); } else { if(!s.count(d1)) { s[d1] = h1; return; } int tmp = s[d1]; if(tmp > h1)s[d1] = h1; } } void DSU(int u , int p) { int bigchild = -1; for(auto c : v[u]) if(c.first != p && (bigchild == -1 || sz[bigchild] < sz[c.first])) bigchild = c.first; for(auto c : v[u]) if(c.first != p && c.first != bigchild) DSU(c.first , u); if(bigchild != -1) { DSU(bigchild , u); vec[u] = vec[bigchild]; } else vec[u] = new unordered_map<ll,int>; add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 0); add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 1); for(auto c : v[u]) if(c.first != p && c.first != bigchild){ for(auto d : (*vec[c.first])) add(*vec[u] , d.second , d.first , h[u] , dep[u] , 1); for(auto d : (*vec[c.first])) add(*vec[u] , d.second , d.first , h[u] , dep[u] , 0); } } int best_path(int N, int K, int H[][2], int L[]) { n = N;k = K; for(int i = 0 ; i < n - 1 ; ++i){ int a = H[i][0] , b = H[i][1] , c = L[i]; ++a;++b; v[a].pb({b,c}); v[b].pb({a,c}); } DFS1(1 ,0); DSU(1 ,0); if(res == maxn)return -1; else return res; }

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

1 | Correct | 9 ms | 5248 KB | Output is correct |

2 | Correct | 7 ms | 5120 KB | Output is correct |

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

4 | Correct | 6 ms | 4992 KB | Output is correct |

5 | Correct | 7 ms | 5120 KB | Output is correct |

6 | Correct | 7 ms | 5120 KB | Output is correct |

7 | Correct | 7 ms | 5120 KB | Output is correct |

8 | Correct | 8 ms | 5120 KB | Output is correct |

9 | Correct | 7 ms | 5120 KB | Output is correct |

10 | Correct | 8 ms | 5120 KB | Output is correct |

11 | Correct | 6 ms | 5120 KB | Output is correct |

12 | Correct | 7 ms | 5120 KB | Output is correct |

13 | Correct | 7 ms | 5120 KB | Output is correct |

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

15 | Correct | 8 ms | 5120 KB | Output is correct |

16 | Correct | 8 ms | 5120 KB | Output is correct |

17 | Correct | 9 ms | 5120 KB | Output is correct |

18 | Correct | 8 ms | 5120 KB | Output is correct |

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

1 | Correct | 9 ms | 5248 KB | Output is correct |

2 | Correct | 7 ms | 5120 KB | Output is correct |

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

4 | Correct | 6 ms | 4992 KB | Output is correct |

5 | Correct | 7 ms | 5120 KB | Output is correct |

6 | Correct | 7 ms | 5120 KB | Output is correct |

7 | Correct | 7 ms | 5120 KB | Output is correct |

8 | Correct | 8 ms | 5120 KB | Output is correct |

9 | Correct | 7 ms | 5120 KB | Output is correct |

10 | Correct | 8 ms | 5120 KB | Output is correct |

11 | Correct | 6 ms | 5120 KB | Output is correct |

12 | Correct | 7 ms | 5120 KB | Output is correct |

13 | Correct | 7 ms | 5120 KB | Output is correct |

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

15 | Correct | 8 ms | 5120 KB | Output is correct |

16 | Correct | 8 ms | 5120 KB | Output is correct |

17 | Correct | 9 ms | 5120 KB | Output is correct |

18 | Correct | 8 ms | 5120 KB | Output is correct |

19 | Correct | 7 ms | 5092 KB | Output is correct |

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

21 | Correct | 7 ms | 5248 KB | Output is correct |

22 | Correct | 9 ms | 5376 KB | Output is correct |

23 | Correct | 9 ms | 5376 KB | Output is correct |

24 | Correct | 8 ms | 5376 KB | Output is correct |

25 | Correct | 8 ms | 5376 KB | Output is correct |

26 | Correct | 10 ms | 5248 KB | Output is correct |

27 | Correct | 8 ms | 5220 KB | Output is correct |

28 | Correct | 9 ms | 5376 KB | Output is correct |

29 | Correct | 8 ms | 5248 KB | Output is correct |

30 | Correct | 10 ms | 5376 KB | Output is correct |

31 | Correct | 7 ms | 5248 KB | Output is correct |

32 | Correct | 9 ms | 5376 KB | Output is correct |

33 | Correct | 8 ms | 5376 KB | Output is correct |

34 | Correct | 7 ms | 5248 KB | Output is correct |

35 | Correct | 7 ms | 5248 KB | Output is correct |

36 | Correct | 7 ms | 5248 KB | Output is correct |

37 | Correct | 7 ms | 5248 KB | Output is correct |

38 | Correct | 7 ms | 5248 KB | Output is correct |

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

1 | Correct | 9 ms | 5248 KB | Output is correct |

2 | Correct | 7 ms | 5120 KB | Output is correct |

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

4 | Correct | 6 ms | 4992 KB | Output is correct |

5 | Correct | 7 ms | 5120 KB | Output is correct |

6 | Correct | 7 ms | 5120 KB | Output is correct |

7 | Correct | 7 ms | 5120 KB | Output is correct |

8 | Correct | 8 ms | 5120 KB | Output is correct |

9 | Correct | 7 ms | 5120 KB | Output is correct |

10 | Correct | 8 ms | 5120 KB | Output is correct |

11 | Correct | 6 ms | 5120 KB | Output is correct |

12 | Correct | 7 ms | 5120 KB | Output is correct |

13 | Correct | 7 ms | 5120 KB | Output is correct |

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

15 | Correct | 8 ms | 5120 KB | Output is correct |

16 | Correct | 8 ms | 5120 KB | Output is correct |

17 | Correct | 9 ms | 5120 KB | Output is correct |

18 | Correct | 8 ms | 5120 KB | Output is correct |

19 | Correct | 161 ms | 24788 KB | Output is correct |

20 | Correct | 186 ms | 24720 KB | Output is correct |

21 | Correct | 179 ms | 24824 KB | Output is correct |

22 | Correct | 204 ms | 25468 KB | Output is correct |

23 | Correct | 246 ms | 35140 KB | Output is correct |

24 | Correct | 201 ms | 33372 KB | Output is correct |

25 | Correct | 137 ms | 18496 KB | Output is correct |

26 | Correct | 99 ms | 22520 KB | Output is correct |

27 | Correct | 317 ms | 39516 KB | Output is correct |

28 | Correct | 416 ms | 48312 KB | Output is correct |

29 | Correct | 340 ms | 47520 KB | Output is correct |

30 | Correct | 331 ms | 39544 KB | Output is correct |

31 | Correct | 314 ms | 39416 KB | Output is correct |

32 | Correct | 467 ms | 39660 KB | Output is correct |

33 | Correct | 291 ms | 30072 KB | Output is correct |

34 | Correct | 587 ms | 51964 KB | Output is correct |

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

1 | Correct | 9 ms | 5248 KB | Output is correct |

2 | Correct | 7 ms | 5120 KB | Output is correct |

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

4 | Correct | 6 ms | 4992 KB | Output is correct |

5 | Correct | 7 ms | 5120 KB | Output is correct |

6 | Correct | 7 ms | 5120 KB | Output is correct |

7 | Correct | 7 ms | 5120 KB | Output is correct |

8 | Correct | 8 ms | 5120 KB | Output is correct |

9 | Correct | 7 ms | 5120 KB | Output is correct |

10 | Correct | 8 ms | 5120 KB | Output is correct |

11 | Correct | 6 ms | 5120 KB | Output is correct |

12 | Correct | 7 ms | 5120 KB | Output is correct |

13 | Correct | 7 ms | 5120 KB | Output is correct |

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

15 | Correct | 8 ms | 5120 KB | Output is correct |

16 | Correct | 8 ms | 5120 KB | Output is correct |

17 | Correct | 9 ms | 5120 KB | Output is correct |

18 | Correct | 8 ms | 5120 KB | Output is correct |

19 | Correct | 7 ms | 5092 KB | Output is correct |

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

21 | Correct | 7 ms | 5248 KB | Output is correct |

22 | Correct | 9 ms | 5376 KB | Output is correct |

23 | Correct | 9 ms | 5376 KB | Output is correct |

24 | Correct | 8 ms | 5376 KB | Output is correct |

25 | Correct | 8 ms | 5376 KB | Output is correct |

26 | Correct | 10 ms | 5248 KB | Output is correct |

27 | Correct | 8 ms | 5220 KB | Output is correct |

28 | Correct | 9 ms | 5376 KB | Output is correct |

29 | Correct | 8 ms | 5248 KB | Output is correct |

30 | Correct | 10 ms | 5376 KB | Output is correct |

31 | Correct | 7 ms | 5248 KB | Output is correct |

32 | Correct | 9 ms | 5376 KB | Output is correct |

33 | Correct | 8 ms | 5376 KB | Output is correct |

34 | Correct | 7 ms | 5248 KB | Output is correct |

35 | Correct | 7 ms | 5248 KB | Output is correct |

36 | Correct | 7 ms | 5248 KB | Output is correct |

37 | Correct | 7 ms | 5248 KB | Output is correct |

38 | Correct | 7 ms | 5248 KB | Output is correct |

39 | Correct | 161 ms | 24788 KB | Output is correct |

40 | Correct | 186 ms | 24720 KB | Output is correct |

41 | Correct | 179 ms | 24824 KB | Output is correct |

42 | Correct | 204 ms | 25468 KB | Output is correct |

43 | Correct | 246 ms | 35140 KB | Output is correct |

44 | Correct | 201 ms | 33372 KB | Output is correct |

45 | Correct | 137 ms | 18496 KB | Output is correct |

46 | Correct | 99 ms | 22520 KB | Output is correct |

47 | Correct | 317 ms | 39516 KB | Output is correct |

48 | Correct | 416 ms | 48312 KB | Output is correct |

49 | Correct | 340 ms | 47520 KB | Output is correct |

50 | Correct | 331 ms | 39544 KB | Output is correct |

51 | Correct | 314 ms | 39416 KB | Output is correct |

52 | Correct | 467 ms | 39660 KB | Output is correct |

53 | Correct | 291 ms | 30072 KB | Output is correct |

54 | Correct | 587 ms | 51964 KB | Output is correct |

55 | Correct | 21 ms | 7808 KB | Output is correct |

56 | Correct | 16 ms | 6784 KB | Output is correct |

57 | Correct | 99 ms | 24568 KB | Output is correct |

58 | Correct | 81 ms | 26088 KB | Output is correct |

59 | Correct | 97 ms | 26500 KB | Output is correct |

60 | Correct | 412 ms | 47752 KB | Output is correct |

61 | Correct | 282 ms | 41976 KB | Output is correct |

62 | Correct | 283 ms | 39432 KB | Output is correct |

63 | Correct | 418 ms | 39596 KB | Output is correct |

64 | Correct | 667 ms | 73096 KB | Output is correct |

65 | Correct | 612 ms | 74836 KB | Output is correct |

66 | Correct | 366 ms | 45756 KB | Output is correct |

67 | Correct | 286 ms | 48116 KB | Output is correct |

68 | Correct | 521 ms | 54988 KB | Output is correct |

69 | Correct | 521 ms | 55768 KB | Output is correct |

70 | Correct | 510 ms | 52952 KB | Output is correct |