oj.uz

Submission #372999

# Submission time Handle Problem Language Result Execution time Memory
372999 2021-03-03T00:40:49 Z Kanon Stations (IOI20_stations) C++14
100 / 100
 1190 ms 1128 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> label(int n, int k, vector<int> u, vector<int> v) {
  vector<vector<int>> g(n);
  for(int i = 0; i < n - 1; i++) {
    int a = u[i], b = v[i];
    g[a].push_back(b);
    g[b].push_back(a);
  }
  vector<int> ret(n, -1);
  vector<int> sub(n);
  vector<int> par(n);
  function<void(int, int)> dfs = [&](int v, int p) {
    par[v] = p;
    sub[v] = 1;
    for(int i : g[v]) {
      if(i == p) continue;
      dfs(i, v);
      sub[v] += sub[i];
    }
  };
  dfs(0, -1);
  function<void(int, int, int, bool)> solve = [&](int v, int L, int R, bool head) {
    ret[v] = head ? L : R;
    int st = L + head;
    for(int i : g[v]) {
      if(i == par[v]) continue;
      solve(i, st, st + sub[i] - 1, !head);
      st += sub[i];
    }
  };
  solve(0, 0, n - 1, true);
  return ret;
}
 
int find_next_station(int s, int t, vector<int> c) {
  if(c.size() == 1) return c[0];
  int n = c.size();
  int par = -1;
  for(int i : c) if(par == -1 || abs(s - i) > abs(s - par)) par = i;
  for(int i = 0; i < n; i++) if(c[i] == par) {
    c.erase(c.begin() + i);
    break;
  }
  c.push_back(s);
  sort(c.begin(), c.end());
  int beg = c[0], fin = c[n - 1];
  if(t < beg || t > fin) return par;
  if(beg == s) {
    return *lower_bound(c.begin(), c.end(), t);
  } else {
    return *prev(upper_bound(c.begin(), c.end(), t));
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 936 KB Output is correct
2 Correct 516 ms 920 KB Output is correct
3 Correct 979 ms 756 KB Output is correct
4 Correct 782 ms 736 KB Output is correct
5 Correct 704 ms 868 KB Output is correct
6 Correct 531 ms 948 KB Output is correct
7 Correct 526 ms 1012 KB Output is correct
8 Correct 3 ms 876 KB Output is correct
9 Correct 4 ms 868 KB Output is correct
10 Correct 2 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 756 KB Output is correct
2 Correct 639 ms 780 KB Output is correct
3 Correct 1010 ms 756 KB Output is correct
4 Correct 785 ms 756 KB Output is correct
5 Correct 720 ms 1012 KB Output is correct
6 Correct 564 ms 756 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 1028 KB Output is correct
2 Correct 541 ms 1024 KB Output is correct
3 Correct 971 ms 756 KB Output is correct
4 Correct 752 ms 996 KB Output is correct
5 Correct 777 ms 868 KB Output is correct
6 Correct 566 ms 864 KB Output is correct
7 Correct 514 ms 1092 KB Output is correct
8 Correct 4 ms 736 KB Output is correct
9 Correct 5 ms 756 KB Output is correct
10 Correct 2 ms 756 KB Output is correct
11 Correct 639 ms 736 KB Output is correct
12 Correct 603 ms 1128 KB Output is correct
13 Correct 488 ms 992 KB Output is correct
14 Correct 539 ms 884 KB Output is correct
15 Correct 65 ms 860 KB Output is correct
16 Correct 83 ms 824 KB Output is correct
17 Correct 126 ms 736 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 960 ms 868 KB Output is correct
2 Correct 725 ms 736 KB Output is correct
3 Correct 688 ms 756 KB Output is correct
4 Correct 3 ms 868 KB Output is correct
5 Correct 5 ms 736 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 613 ms 868 KB Output is correct
8 Correct 1190 ms 756 KB Output is correct
9 Correct 701 ms 868 KB Output is correct
10 Correct 620 ms 756 KB Output is correct
11 Correct 6 ms 876 KB Output is correct
12 Correct 6 ms 736 KB Output is correct
13 Correct 6 ms 736 KB Output is correct
14 Correct 6 ms 868 KB Output is correct
15 Correct 2 ms 736 KB Output is correct
16 Correct 588 ms 756 KB Output is correct
17 Correct 502 ms 736 KB Output is correct
18 Correct 570 ms 876 KB Output is correct
19 Correct 609 ms 868 KB Output is correct
20 Correct 621 ms 992 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 1012 KB Output is correct
2 Correct 551 ms 1100 KB Output is correct
3 Correct 1043 ms 756 KB Output is correct
4 Correct 661 ms 876 KB Output is correct
5 Correct 594 ms 1060 KB Output is correct
6 Correct 550 ms 936 KB Output is correct
7 Correct 620 ms 1012 KB Output is correct
8 Correct 3 ms 908 KB Output is correct
9 Correct 5 ms 736 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 547 ms 756 KB Output is correct
12 Correct 574 ms 756 KB Output is correct
13 Correct 990 ms 756 KB Output is correct
14 Correct 706 ms 868 KB Output is correct
15 Correct 661 ms 1012 KB Output is correct
16 Correct 564 ms 788 KB Output is correct
17 Correct 801 ms 868 KB Output is correct
18 Correct 480 ms 968 KB Output is correct
19 Correct 557 ms 884 KB Output is correct
20 Correct 503 ms 736 KB Output is correct
21 Correct 64 ms 860 KB Output is correct
22 Correct 67 ms 756 KB Output is correct
23 Correct 151 ms 784 KB Output is correct
24 Correct 6 ms 868 KB Output is correct
25 Correct 7 ms 736 KB Output is correct
26 Correct 6 ms 868 KB Output is correct
27 Correct 5 ms 868 KB Output is correct
28 Correct 2 ms 756 KB Output is correct
29 Correct 602 ms 756 KB Output is correct
30 Correct 621 ms 868 KB Output is correct
31 Correct 636 ms 868 KB Output is correct
32 Correct 672 ms 868 KB Output is correct
33 Correct 651 ms 1044 KB Output is correct
34 Correct 380 ms 864 KB Output is correct
35 Correct 489 ms 1052 KB Output is correct
36 Correct 468 ms 884 KB Output is correct
37 Correct 520 ms 864 KB Output is correct
38 Correct 505 ms 852 KB Output is correct
39 Correct 495 ms 1096 KB Output is correct
40 Correct 466 ms 1000 KB Output is correct
41 Correct 533 ms 1116 KB Output is correct
42 Correct 65 ms 848 KB Output is correct
43 Correct 127 ms 756 KB Output is correct
44 Correct 130 ms 756 KB Output is correct
45 Correct 143 ms 776 KB Output is correct
46 Correct 371 ms 884 KB Output is correct
47 Correct 354 ms 864 KB Output is correct
48 Correct 81 ms 776 KB Output is correct
49 Correct 61 ms 876 KB Output is correct