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

329690 | 2020-11-22T03:00:55 Z | chenwz | Stations (IOI20_stations) | C++14 | 1016 ms | 1140 KB |

#include "stations.h" #include <vector> void rec(int index, int parent, int pre_order, int &number, std::vector<std::vector<int>>& con, std::vector<int>& labels) { if (pre_order) labels[index] = number++; for (int i : con[index]) { if (i == parent) continue; rec(i, index, !pre_order, number, con, labels); } if (!pre_order) labels[index] = number++; } std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) { std::vector<int> labels(n); std::vector<std::vector<int>> con(n, std::vector<int>()); for (int i = 0; i < u.size(); i++) { con[u[i]].push_back(v[i]); con[v[i]].push_back(u[i]); } int number = 0; rec(0, -1, true, number, con, labels); return labels; } int find_next_station(int s, int t, std::vector<int> c) { if (c[0] > s) { // Case 1: node s is in pre_order level. // All the neighbors are higher than s. if (t < s) { // The target is smaller than the source. // The target is definitely not in this subtree, go to parent. return c.back(); } if (t > c.back()) { // The target is higher than the largest neighbor. // The target cannot be in this subtree, go to parent. return c.back(); } // The target is in this subtree. // Pick the smallest child that's at least the target. int next = 0; while (c[next] < t) next++; return c[next]; } // Case 2: node s is in the post_order level. if (t < c[0]) { // The target is smaller than the pre_order root c[0], // thus not in this subtree, go to the root. return c[0]; } if (t > s) { // The target is higher than this post_order value. // Thus it's not in this subtree, go to the root. return c[0]; } int next = c.size() - 1; while (c[next] > t) next--; return c[next]; }

### Compilation message

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

1 | Correct | 521 ms | 884 KB | Output is correct |

2 | Correct | 489 ms | 1044 KB | Output is correct |

3 | Correct | 881 ms | 920 KB | Output is correct |

4 | Correct | 636 ms | 1140 KB | Output is correct |

5 | Correct | 657 ms | 800 KB | Output is correct |

6 | Correct | 440 ms | 884 KB | Output is correct |

7 | Correct | 493 ms | 1128 KB | Output is correct |

8 | Correct | 2 ms | 888 KB | Output is correct |

9 | Correct | 3 ms | 736 KB | Output is correct |

10 | Correct | 0 ms | 736 KB | Output is correct |

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

1 | Correct | 509 ms | 932 KB | Output is correct |

2 | Correct | 528 ms | 800 KB | Output is correct |

3 | Correct | 909 ms | 920 KB | Output is correct |

4 | Correct | 698 ms | 860 KB | Output is correct |

5 | Correct | 643 ms | 884 KB | Output is correct |

6 | Correct | 430 ms | 756 KB | Output is correct |

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

1 | Correct | 643 ms | 972 KB | Output is correct |

2 | Correct | 432 ms | 972 KB | Output is correct |

3 | Correct | 861 ms | 888 KB | Output is correct |

4 | Correct | 654 ms | 880 KB | Output is correct |

5 | Correct | 587 ms | 752 KB | Output is correct |

6 | Correct | 423 ms | 1104 KB | Output is correct |

7 | Correct | 532 ms | 884 KB | Output is correct |

8 | Correct | 2 ms | 928 KB | Output is correct |

9 | Correct | 5 ms | 880 KB | Output is correct |

10 | Correct | 0 ms | 736 KB | Output is correct |

11 | Correct | 763 ms | 756 KB | Output is correct |

12 | Correct | 462 ms | 928 KB | Output is correct |

13 | Correct | 493 ms | 960 KB | Output is correct |

14 | Correct | 516 ms | 808 KB | Output is correct |

15 | Correct | 62 ms | 756 KB | Output is correct |

16 | Correct | 64 ms | 736 KB | Output is correct |

17 | Correct | 96 ms | 808 KB | Output is correct |

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

1 | Correct | 1016 ms | 864 KB | Output is correct |

2 | Correct | 626 ms | 880 KB | Output is correct |

3 | Correct | 578 ms | 888 KB | Output is correct |

4 | Correct | 2 ms | 888 KB | Output is correct |

5 | Correct | 4 ms | 880 KB | Output is correct |

6 | Correct | 0 ms | 756 KB | Output is correct |

7 | Correct | 589 ms | 736 KB | Output is correct |

8 | Correct | 841 ms | 756 KB | Output is correct |

9 | Correct | 642 ms | 880 KB | Output is correct |

10 | Correct | 635 ms | 880 KB | Output is correct |

11 | Correct | 4 ms | 888 KB | Output is correct |

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

13 | Correct | 5 ms | 928 KB | Output is correct |

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

15 | Correct | 1 ms | 756 KB | Output is correct |

16 | Correct | 494 ms | 884 KB | Output is correct |

17 | Correct | 490 ms | 880 KB | Output is correct |

18 | Correct | 496 ms | 880 KB | Output is correct |

19 | Correct | 510 ms | 880 KB | Output is correct |

20 | Correct | 489 ms | 880 KB | Output is correct |

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

1 | Correct | 508 ms | 896 KB | Output is correct |

2 | Correct | 436 ms | 864 KB | Output is correct |

3 | Correct | 840 ms | 736 KB | Output is correct |

4 | Correct | 668 ms | 880 KB | Output is correct |

5 | Correct | 566 ms | 864 KB | Output is correct |

6 | Correct | 442 ms | 864 KB | Output is correct |

7 | Correct | 424 ms | 756 KB | Output is correct |

8 | Correct | 2 ms | 888 KB | Output is correct |

9 | Correct | 4 ms | 796 KB | Output is correct |

10 | Correct | 1 ms | 736 KB | Output is correct |

11 | Correct | 445 ms | 736 KB | Output is correct |

12 | Correct | 506 ms | 940 KB | Output is correct |

13 | Correct | 857 ms | 880 KB | Output is correct |

14 | Correct | 627 ms | 1008 KB | Output is correct |

15 | Correct | 579 ms | 804 KB | Output is correct |

16 | Correct | 428 ms | 816 KB | Output is correct |

17 | Correct | 574 ms | 880 KB | Output is correct |

18 | Correct | 442 ms | 1128 KB | Output is correct |

19 | Correct | 473 ms | 980 KB | Output is correct |

20 | Correct | 520 ms | 736 KB | Output is correct |

21 | Correct | 51 ms | 912 KB | Output is correct |

22 | Correct | 66 ms | 736 KB | Output is correct |

23 | Correct | 102 ms | 992 KB | Output is correct |

24 | Correct | 6 ms | 736 KB | Output is correct |

25 | Correct | 6 ms | 756 KB | Output is correct |

26 | Correct | 6 ms | 880 KB | Output is correct |

27 | Correct | 4 ms | 736 KB | Output is correct |

28 | Correct | 1 ms | 736 KB | Output is correct |

29 | Correct | 524 ms | 880 KB | Output is correct |

30 | Correct | 541 ms | 756 KB | Output is correct |

31 | Correct | 548 ms | 1008 KB | Output is correct |

32 | Correct | 619 ms | 756 KB | Output is correct |

33 | Correct | 605 ms | 756 KB | Output is correct |

34 | Correct | 384 ms | 884 KB | Output is correct |

35 | Correct | 459 ms | 1056 KB | Output is correct |

36 | Correct | 415 ms | 984 KB | Output is correct |

37 | Correct | 503 ms | 912 KB | Output is correct |

38 | Correct | 543 ms | 936 KB | Output is correct |

39 | Correct | 442 ms | 992 KB | Output is correct |

40 | Correct | 469 ms | 868 KB | Output is correct |

41 | Correct | 523 ms | 864 KB | Output is correct |

42 | Correct | 64 ms | 820 KB | Output is correct |

43 | Correct | 127 ms | 884 KB | Output is correct |

44 | Correct | 123 ms | 1012 KB | Output is correct |

45 | Correct | 210 ms | 1032 KB | Output is correct |

46 | Correct | 346 ms | 812 KB | Output is correct |

47 | Correct | 299 ms | 764 KB | Output is correct |

48 | Correct | 65 ms | 796 KB | Output is correct |

49 | Correct | 62 ms | 936 KB | Output is correct |