oj.uz

Submission #807539

# Submission time Handle Problem Language Result Execution time Memory
807539 2023-08-04T19:09:01 Z dong_liu Jail (JOI22_jail) C++17
100 / 100
 1231 ms 307488 KB 
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 1.2e5, H = 17, N_ = N + 2 * N * H;

vector<int> g[N], q[N_];
int p[H][N], d[N], w[N_];

inline int z(int i, int h, int t) { return (i * H + h) * 2 + t; }

void dfs(int i) {
  for (int h = 0; h < H - 1; h++) {
    p[h + 1][i] = p[h][p[h][i]];
    q[z(i, h, 0)].push_back(z(i, h + 1, 0));
    q[z(p[h][i], h, 0)].push_back(z(i, h + 1, 0));
    q[z(i, h + 1, 1)].push_back(z(i, h, 1));
    q[z(i, h + 1, 1)].push_back(z(p[h][i], h, 1));
  }
  for (int j : g[i])
    if (p[0][i] != j) {
      p[0][j] = i;
      d[j] = d[i] + 1;
      dfs(j);
    }
}

int lca(int i, int j) {
  if (d[i] < d[j]) swap(i, j);
  int k = d[i] - d[j];
  for (int h = 0; h < H; h++)
    if (k >> h & 1) i = p[h][i];
  if (i == j) return i;
  for (int h = H - 1; h >= 0; h--)
    if (p[h][i] != p[h][j]) i = p[h][i], j = p[h][j];
  return p[0][i];
}

template <class F>
void up(int i, int k, const F& f) {
  if (k < 0) return;
  for (int h = 0; h < H; h++)
    if (k >> h & 1) f(i, h), i = p[h][i];
  f(i, 0);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    for (int h = 0; h < n - 1; h++) {
      int i, j;
      cin >> i >> j, i--, j--;
      g[i].push_back(j), g[j].push_back(i);
    }
    dfs(0);
    int m;
    cin >> m;
    for (int h = 0; h < m; h++) {
      int i, j;
      cin >> i >> j, i--, j--;
      q[n * H * 2 + h].push_back(z(i, 0, 0));
      q[z(j, 0, 1)].push_back(n * H * 2 + h);
      int f = lca(i, j);
      if (i != f) {
        up(p[0][i], d[i] - d[f] - 1,
           [&](int u, int v) { q[z(u, v, 0)].push_back(n * H * 2 + h); });
        up(j, d[j] - d[f] - 1,
           [&](int u, int v) { q[z(u, v, 0)].push_back(n * H * 2 + h); });
      } else
        up(j, d[j] - d[f] - 1,
           [&](int u, int v) { q[z(u, v, 0)].push_back(n * H * 2 + h); });
      if (j != f) {
        up(p[0][j], d[j] - d[f] - 1,
           [&](int u, int v) { q[n * H * 2 + h].push_back(z(u, v, 1)); });
        up(i, d[i] - d[f] - 1,
           [&](int u, int v) { q[n * H * 2 + h].push_back(z(u, v, 1)); });
      } else
        up(i, d[i] - d[f] - 1,
           [&](int u, int v) { q[n * H * 2 + h].push_back(z(u, v, 1)); });
    }
    for (int i = 0; i < n * H * 2 + m; i++)
      for (int j : q[i]) w[j]++;
    vector<int> o;
    for (int i = 0; i < n * H * 2 + m; i++)
      if (!w[i]) o.push_back(i);
    for (int u = 0; u < (int)o.size(); u++) {
      int i = o[u];
      for (int j : q[i])
        if (--w[j] == 0) o.push_back(j);
    }
    cout << ((int)o.size() == n * H * 2 + m ? "Yes\n" : "No\n");
    for (int i = 0; i < n; i++) g[i].clear();
    for (int i = 0; i < n * H * 2 + m; i++) q[i].clear(), w[i] = 0;
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 101844 KB Output is correct
2 Correct 47 ms 101864 KB Output is correct
3 Correct 46 ms 101836 KB Output is correct
4 Correct 74 ms 102352 KB Output is correct
5 Correct 107 ms 102804 KB Output is correct
6 Correct 49 ms 102220 KB Output is correct
7 Correct 49 ms 102236 KB Output is correct
8 Correct 49 ms 102372 KB Output is correct
9 Correct 202 ms 113248 KB Output is correct
10 Correct 999 ms 281596 KB Output is correct
11 Correct 66 ms 102044 KB Output is correct
12 Correct 115 ms 102964 KB Output is correct
13 Correct 997 ms 286224 KB Output is correct
14 Correct 894 ms 277852 KB Output is correct
15 Correct 896 ms 273404 KB Output is correct
16 Correct 1128 ms 281576 KB Output is correct
17 Correct 1107 ms 289024 KB Output is correct
18 Correct 1062 ms 307488 KB Output is correct
19 Correct 1096 ms 289140 KB Output is correct
20 Correct 1008 ms 289032 KB Output is correct
21 Correct 841 ms 275056 KB Output is correct
22 Correct 926 ms 278048 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 101764 KB Output is correct
2 Correct 58 ms 101828 KB Output is correct
3 Correct 55 ms 102220 KB Output is correct
4 Correct 56 ms 102268 KB Output is correct
5 Correct 55 ms 102296 KB Output is correct
6 Correct 56 ms 102304 KB Output is correct
7 Correct 53 ms 102352 KB Output is correct
8 Correct 64 ms 102232 KB Output is correct
9 Correct 58 ms 102356 KB Output is correct
10 Correct 56 ms 102220 KB Output is correct
11 Correct 55 ms 102256 KB Output is correct
12 Correct 53 ms 102304 KB Output is correct
13 Correct 53 ms 102280 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 101764 KB Output is correct
2 Correct 58 ms 101828 KB Output is correct
3 Correct 55 ms 102220 KB Output is correct
4 Correct 56 ms 102268 KB Output is correct
5 Correct 55 ms 102296 KB Output is correct
6 Correct 56 ms 102304 KB Output is correct
7 Correct 53 ms 102352 KB Output is correct
8 Correct 64 ms 102232 KB Output is correct
9 Correct 58 ms 102356 KB Output is correct
10 Correct 56 ms 102220 KB Output is correct
11 Correct 55 ms 102256 KB Output is correct
12 Correct 53 ms 102304 KB Output is correct
13 Correct 53 ms 102280 KB Output is correct
14 Correct 52 ms 101800 KB Output is correct
15 Correct 50 ms 101860 KB Output is correct
16 Correct 60 ms 102220 KB Output is correct
17 Correct 53 ms 102316 KB Output is correct
18 Correct 53 ms 102328 KB Output is correct
19 Correct 59 ms 101828 KB Output is correct
20 Correct 55 ms 102376 KB Output is correct
21 Correct 54 ms 102220 KB Output is correct
22 Correct 55 ms 102280 KB Output is correct
23 Correct 64 ms 101820 KB Output is correct
24 Correct 58 ms 101964 KB Output is correct
25 Correct 55 ms 102220 KB Output is correct
26 Correct 52 ms 102256 KB Output is correct
27 Correct 54 ms 102260 KB Output is correct
28 Correct 51 ms 101860 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 101764 KB Output is correct
2 Correct 58 ms 101828 KB Output is correct
3 Correct 55 ms 102220 KB Output is correct
4 Correct 56 ms 102268 KB Output is correct
5 Correct 55 ms 102296 KB Output is correct
6 Correct 56 ms 102304 KB Output is correct
7 Correct 53 ms 102352 KB Output is correct
8 Correct 64 ms 102232 KB Output is correct
9 Correct 58 ms 102356 KB Output is correct
10 Correct 56 ms 102220 KB Output is correct
11 Correct 55 ms 102256 KB Output is correct
12 Correct 53 ms 102304 KB Output is correct
13 Correct 53 ms 102280 KB Output is correct
14 Correct 52 ms 101800 KB Output is correct
15 Correct 50 ms 101860 KB Output is correct
16 Correct 60 ms 102220 KB Output is correct
17 Correct 53 ms 102316 KB Output is correct
18 Correct 53 ms 102328 KB Output is correct
19 Correct 59 ms 101828 KB Output is correct
20 Correct 55 ms 102376 KB Output is correct
21 Correct 54 ms 102220 KB Output is correct
22 Correct 55 ms 102280 KB Output is correct
23 Correct 64 ms 101820 KB Output is correct
24 Correct 58 ms 101964 KB Output is correct
25 Correct 55 ms 102220 KB Output is correct
26 Correct 52 ms 102256 KB Output is correct
27 Correct 54 ms 102260 KB Output is correct
28 Correct 51 ms 101860 KB Output is correct
29 Correct 54 ms 102348 KB Output is correct
30 Correct 54 ms 102280 KB Output is correct
31 Correct 54 ms 102252 KB Output is correct
32 Correct 55 ms 102276 KB Output is correct
33 Correct 54 ms 102284 KB Output is correct
34 Correct 56 ms 102204 KB Output is correct
35 Correct 61 ms 102236 KB Output is correct
36 Correct 52 ms 102228 KB Output is correct
37 Correct 53 ms 102216 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 101764 KB Output is correct
2 Correct 58 ms 101828 KB Output is correct
3 Correct 55 ms 102220 KB Output is correct
4 Correct 56 ms 102268 KB Output is correct
5 Correct 55 ms 102296 KB Output is correct
6 Correct 56 ms 102304 KB Output is correct
7 Correct 53 ms 102352 KB Output is correct
8 Correct 64 ms 102232 KB Output is correct
9 Correct 58 ms 102356 KB Output is correct
10 Correct 56 ms 102220 KB Output is correct
11 Correct 55 ms 102256 KB Output is correct
12 Correct 53 ms 102304 KB Output is correct
13 Correct 53 ms 102280 KB Output is correct
14 Correct 52 ms 101800 KB Output is correct
15 Correct 50 ms 101860 KB Output is correct
16 Correct 60 ms 102220 KB Output is correct
17 Correct 53 ms 102316 KB Output is correct
18 Correct 53 ms 102328 KB Output is correct
19 Correct 59 ms 101828 KB Output is correct
20 Correct 55 ms 102376 KB Output is correct
21 Correct 54 ms 102220 KB Output is correct
22 Correct 55 ms 102280 KB Output is correct
23 Correct 64 ms 101820 KB Output is correct
24 Correct 58 ms 101964 KB Output is correct
25 Correct 55 ms 102220 KB Output is correct
26 Correct 52 ms 102256 KB Output is correct
27 Correct 54 ms 102260 KB Output is correct
28 Correct 51 ms 101860 KB Output is correct
29 Correct 54 ms 102348 KB Output is correct
30 Correct 54 ms 102280 KB Output is correct
31 Correct 54 ms 102252 KB Output is correct
32 Correct 55 ms 102276 KB Output is correct
33 Correct 54 ms 102284 KB Output is correct
34 Correct 56 ms 102204 KB Output is correct
35 Correct 61 ms 102236 KB Output is correct
36 Correct 52 ms 102228 KB Output is correct
37 Correct 53 ms 102216 KB Output is correct
38 Correct 273 ms 113280 KB Output is correct
39 Correct 1034 ms 281672 KB Output is correct
40 Correct 311 ms 113560 KB Output is correct
41 Correct 296 ms 113216 KB Output is correct
42 Correct 205 ms 114040 KB Output is correct
43 Correct 296 ms 114196 KB Output is correct
44 Correct 70 ms 103940 KB Output is correct
45 Correct 971 ms 275048 KB Output is correct
46 Correct 927 ms 275128 KB Output is correct
47 Correct 1004 ms 275524 KB Output is correct
48 Correct 1089 ms 275600 KB Output is correct
49 Correct 777 ms 276036 KB Output is correct
50 Correct 843 ms 276060 KB Output is correct
51 Correct 839 ms 276172 KB Output is correct
52 Correct 835 ms 276172 KB Output is correct
53 Correct 112 ms 116196 KB Output is correct
54 Correct 969 ms 275608 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 101772 KB Output is correct
2 Correct 53 ms 101784 KB Output is correct
3 Correct 55 ms 101868 KB Output is correct
4 Correct 54 ms 101836 KB Output is correct
5 Correct 66 ms 102036 KB Output is correct
6 Correct 55 ms 102308 KB Output is correct
7 Correct 64 ms 102360 KB Output is correct
8 Correct 61 ms 101848 KB Output is correct
9 Correct 53 ms 101864 KB Output is correct
10 Correct 53 ms 102016 KB Output is correct
11 Correct 53 ms 101900 KB Output is correct
12 Correct 55 ms 102228 KB Output is correct
13 Correct 96 ms 102660 KB Output is correct
14 Correct 130 ms 102852 KB Output is correct
15 Correct 111 ms 102720 KB Output is correct
16 Correct 947 ms 276872 KB Output is correct
17 Correct 906 ms 274808 KB Output is correct
18 Correct 1047 ms 281564 KB Output is correct
19 Correct 959 ms 278012 KB Output is correct
20 Correct 953 ms 277984 KB Output is correct
21 Correct 954 ms 277904 KB Output is correct
22 Correct 865 ms 282792 KB Output is correct
23 Correct 771 ms 274416 KB Output is correct
24 Correct 932 ms 282712 KB Output is correct
25 Correct 934 ms 282744 KB Output is correct
26 Correct 949 ms 282688 KB Output is correct
27 Correct 1138 ms 302844 KB Output is correct
28 Correct 881 ms 278000 KB Output is correct
29 Correct 866 ms 278192 KB Output is correct
30 Correct 1033 ms 280752 KB Output is correct
31 Correct 926 ms 280764 KB Output is correct
32 Correct 998 ms 280708 KB Output is correct
33 Correct 876 ms 272464 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 101844 KB Output is correct
2 Correct 47 ms 101864 KB Output is correct
3 Correct 46 ms 101836 KB Output is correct
4 Correct 74 ms 102352 KB Output is correct
5 Correct 107 ms 102804 KB Output is correct
6 Correct 49 ms 102220 KB Output is correct
7 Correct 49 ms 102236 KB Output is correct
8 Correct 49 ms 102372 KB Output is correct
9 Correct 202 ms 113248 KB Output is correct
10 Correct 999 ms 281596 KB Output is correct
11 Correct 66 ms 102044 KB Output is correct
12 Correct 115 ms 102964 KB Output is correct
13 Correct 997 ms 286224 KB Output is correct
14 Correct 894 ms 277852 KB Output is correct
15 Correct 896 ms 273404 KB Output is correct
16 Correct 1128 ms 281576 KB Output is correct
17 Correct 1107 ms 289024 KB Output is correct
18 Correct 1062 ms 307488 KB Output is correct
19 Correct 1096 ms 289140 KB Output is correct
20 Correct 1008 ms 289032 KB Output is correct
21 Correct 841 ms 275056 KB Output is correct
22 Correct 926 ms 278048 KB Output is correct
23 Correct 52 ms 101764 KB Output is correct
24 Correct 58 ms 101828 KB Output is correct
25 Correct 55 ms 102220 KB Output is correct
26 Correct 56 ms 102268 KB Output is correct
27 Correct 55 ms 102296 KB Output is correct
28 Correct 56 ms 102304 KB Output is correct
29 Correct 53 ms 102352 KB Output is correct
30 Correct 64 ms 102232 KB Output is correct
31 Correct 58 ms 102356 KB Output is correct
32 Correct 56 ms 102220 KB Output is correct
33 Correct 55 ms 102256 KB Output is correct
34 Correct 53 ms 102304 KB Output is correct
35 Correct 53 ms 102280 KB Output is correct
36 Correct 52 ms 101800 KB Output is correct
37 Correct 50 ms 101860 KB Output is correct
38 Correct 60 ms 102220 KB Output is correct
39 Correct 53 ms 102316 KB Output is correct
40 Correct 53 ms 102328 KB Output is correct
41 Correct 59 ms 101828 KB Output is correct
42 Correct 55 ms 102376 KB Output is correct
43 Correct 54 ms 102220 KB Output is correct
44 Correct 55 ms 102280 KB Output is correct
45 Correct 64 ms 101820 KB Output is correct
46 Correct 58 ms 101964 KB Output is correct
47 Correct 55 ms 102220 KB Output is correct
48 Correct 52 ms 102256 KB Output is correct
49 Correct 54 ms 102260 KB Output is correct
50 Correct 51 ms 101860 KB Output is correct
51 Correct 54 ms 102348 KB Output is correct
52 Correct 54 ms 102280 KB Output is correct
53 Correct 54 ms 102252 KB Output is correct
54 Correct 55 ms 102276 KB Output is correct
55 Correct 54 ms 102284 KB Output is correct
56 Correct 56 ms 102204 KB Output is correct
57 Correct 61 ms 102236 KB Output is correct
58 Correct 52 ms 102228 KB Output is correct
59 Correct 53 ms 102216 KB Output is correct
60 Correct 273 ms 113280 KB Output is correct
61 Correct 1034 ms 281672 KB Output is correct
62 Correct 311 ms 113560 KB Output is correct
63 Correct 296 ms 113216 KB Output is correct
64 Correct 205 ms 114040 KB Output is correct
65 Correct 296 ms 114196 KB Output is correct
66 Correct 70 ms 103940 KB Output is correct
67 Correct 971 ms 275048 KB Output is correct
68 Correct 927 ms 275128 KB Output is correct
69 Correct 1004 ms 275524 KB Output is correct
70 Correct 1089 ms 275600 KB Output is correct
71 Correct 777 ms 276036 KB Output is correct
72 Correct 843 ms 276060 KB Output is correct
73 Correct 839 ms 276172 KB Output is correct
74 Correct 835 ms 276172 KB Output is correct
75 Correct 112 ms 116196 KB Output is correct
76 Correct 969 ms 275608 KB Output is correct
77 Correct 53 ms 101772 KB Output is correct
78 Correct 53 ms 101784 KB Output is correct
79 Correct 55 ms 101868 KB Output is correct
80 Correct 54 ms 101836 KB Output is correct
81 Correct 66 ms 102036 KB Output is correct
82 Correct 55 ms 102308 KB Output is correct
83 Correct 64 ms 102360 KB Output is correct
84 Correct 61 ms 101848 KB Output is correct
85 Correct 53 ms 101864 KB Output is correct
86 Correct 53 ms 102016 KB Output is correct
87 Correct 53 ms 101900 KB Output is correct
88 Correct 55 ms 102228 KB Output is correct
89 Correct 96 ms 102660 KB Output is correct
90 Correct 130 ms 102852 KB Output is correct
91 Correct 111 ms 102720 KB Output is correct
92 Correct 947 ms 276872 KB Output is correct
93 Correct 906 ms 274808 KB Output is correct
94 Correct 1047 ms 281564 KB Output is correct
95 Correct 959 ms 278012 KB Output is correct
96 Correct 953 ms 277984 KB Output is correct
97 Correct 954 ms 277904 KB Output is correct
98 Correct 865 ms 282792 KB Output is correct
99 Correct 771 ms 274416 KB Output is correct
100 Correct 932 ms 282712 KB Output is correct
101 Correct 934 ms 282744 KB Output is correct
102 Correct 949 ms 282688 KB Output is correct
103 Correct 1138 ms 302844 KB Output is correct
104 Correct 881 ms 278000 KB Output is correct
105 Correct 866 ms 278192 KB Output is correct
106 Correct 1033 ms 280752 KB Output is correct
107 Correct 926 ms 280764 KB Output is correct
108 Correct 998 ms 280708 KB Output is correct
109 Correct 876 ms 272464 KB Output is correct
110 Correct 136 ms 103132 KB Output is correct
111 Correct 108 ms 102776 KB Output is correct
112 Correct 1050 ms 278580 KB Output is correct
113 Correct 1063 ms 279084 KB Output is correct
114 Correct 843 ms 278472 KB Output is correct
115 Correct 604 ms 276292 KB Output is correct
116 Correct 1111 ms 281484 KB Output is correct
117 Correct 1193 ms 283052 KB Output is correct
118 Correct 1073 ms 275632 KB Output is correct
119 Correct 1059 ms 275684 KB Output is correct
120 Correct 112 ms 117656 KB Output is correct
121 Correct 1133 ms 282024 KB Output is correct
122 Correct 1149 ms 281980 KB Output is correct
123 Correct 1210 ms 280548 KB Output is correct
124 Correct 931 ms 272260 KB Output is correct
125 Correct 1141 ms 280988 KB Output is correct
126 Correct 1231 ms 283912 KB Output is correct
127 Correct 1096 ms 287880 KB Output is correct
128 Correct 975 ms 287736 KB Output is correct
129 Correct 1104 ms 288036 KB Output is correct
130 Correct 1098 ms 288024 KB Output is correct