oj.uz

Submission #556881

# Submission time Handle Problem Language Result Execution time Memory
556881 2022-05-04T09:18:25 Z Soumya1 Inside information (BOI21_servers) C++17
50 / 100
 184 ms 31244 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 120005;
const int lg = 18;
int par[mxN][lg];
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> ad[mxN];
int upto_dec[mxN], upto_inc[mxN];
int dep[mxN];
int edge[mxN];
int kth_ancestor(int u, int k) {
  for (int j = lg - 1; j >= 0; j--) {
    if (k & (1 << j)) u = par[u][j];
  }
  return u;
}
pair<int, bool> __lca(int u, int v, int lim) {
  int _u = u, _v = v;
  bool swapped = false;
  if (dep[u] > dep[v]) swap(u, v), swapped = true;
  v = kth_ancestor(v, dep[v] - dep[u]);
  if (u == v) {
    if (_u == _v) return {u, true};
    if (dep[_u] > dep[_v]) {
      return {u, edge[_u] < lim};
    }
    int vv = kth_ancestor(_v, dep[_v] - dep[_u] - 1);
    if (edge[vv] < lim) return {u,  true};
    return {u, false};
  }
  for (int j = lg - 1; j >= 0; j--) {
    if (par[u][j] != par[v][j]) u = par[u][j], v = par[v][j];
  }
  if (swapped) swap(u, v);
  return {par[u][0], (edge[_u] < lim && edge[u] > edge[v])};
}
void dfs(int u, int p, int last) {
  for (int j = 1; j < lg; j++) par[u][j] = par[par[u][j - 1]][j - 1];
  for (auto [v, ee] : ad[u]) {
    if (v == p) continue;
    edge[v] = ee;
    par[v][0] = u;
    dep[v] = dep[u] + 1;
    if (last > ee) {
      upto_dec[v] = upto_dec[u];
      upto_inc[v] = dep[u];
    } else {
      upto_inc[v] = upto_inc[u];
      upto_dec[v] = dep[u];
    }
    dfs(v, u, ee);
  }
}
void testCase() {
  int n, q;
  cin >> n >> q;
  int cur_edge = 0;
  for (int i = 0; i < n + q - 1; i++) {
    char c;
    cin >> c;
    if (c == 'S') {
      int u, v;
      cin >> u >> v;
      ad[u].push_back({v,  cur_edge});
      ad[v].push_back({u, cur_edge});
      cur_edge++;
    } else if (c == 'Q') {
      int u, v;
      cin >> u >> v;
      queries.push_back({u, v, cur_edge});
    } else {
      int u;
      cin >> u;
      queries.push_back({0, u, cur_edge});
    }
  }
  dep[1] = 0, par[1][0] = 1, upto_inc[1] = upto_dec[1] = 0;
  dfs(1, -1, -1);
  for (auto [u, v, ee] : queries) {
    if (u) {
      auto [l, ok] = __lca(u, v, ee);
      if (upto_dec[v] > dep[l]) {
        cout << "no\n";
      } else if (upto_inc[u] > dep[l]) {
        cout << "no\n";
      } else if (!ok) {
        cout << "no\n";
      } else {
        cout << "yes\n";
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5052 KB Output is correct
2 Correct 43 ms 6188 KB Output is correct
3 Correct 41 ms 6448 KB Output is correct
4 Correct 47 ms 6408 KB Output is correct
5 Correct 40 ms 6736 KB Output is correct
6 Correct 41 ms 6336 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5052 KB Output is correct
2 Correct 43 ms 6188 KB Output is correct
3 Correct 41 ms 6448 KB Output is correct
4 Correct 47 ms 6408 KB Output is correct
5 Correct 40 ms 6736 KB Output is correct
6 Correct 41 ms 6336 KB Output is correct
7 Incorrect 33 ms 5692 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4972 KB Output is correct
2 Correct 113 ms 20804 KB Output is correct
3 Correct 118 ms 20696 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4972 KB Output is correct
2 Correct 113 ms 20804 KB Output is correct
3 Correct 118 ms 20696 KB Output is correct
4 Incorrect 32 ms 5476 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5076 KB Output is correct
2 Correct 128 ms 31152 KB Output is correct
3 Correct 113 ms 31168 KB Output is correct
4 Correct 107 ms 31100 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5076 KB Output is correct
2 Correct 128 ms 31152 KB Output is correct
3 Correct 113 ms 31168 KB Output is correct
4 Correct 107 ms 31100 KB Output is correct
5 Incorrect 28 ms 5536 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5072 KB Output is correct
2 Correct 106 ms 20868 KB Output is correct
3 Correct 112 ms 21196 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5072 KB Output is correct
2 Correct 106 ms 20868 KB Output is correct
3 Correct 112 ms 21196 KB Output is correct
4 Incorrect 33 ms 5484 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5056 KB Output is correct
2 Correct 136 ms 31244 KB Output is correct
3 Correct 116 ms 31012 KB Output is correct
4 Correct 106 ms 31040 KB Output is correct
5 Correct 32 ms 5476 KB Output is correct
6 Correct 109 ms 20628 KB Output is correct
7 Correct 112 ms 21184 KB Output is correct
8 Correct 144 ms 21504 KB Output is correct
9 Correct 134 ms 21648 KB Output is correct
10 Correct 148 ms 26764 KB Output is correct
11 Correct 168 ms 25856 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5056 KB Output is correct
2 Correct 136 ms 31244 KB Output is correct
3 Correct 116 ms 31012 KB Output is correct
4 Correct 106 ms 31040 KB Output is correct
5 Correct 32 ms 5476 KB Output is correct
6 Correct 109 ms 20628 KB Output is correct
7 Correct 112 ms 21184 KB Output is correct
8 Correct 144 ms 21504 KB Output is correct
9 Correct 134 ms 21648 KB Output is correct
10 Correct 148 ms 26764 KB Output is correct
11 Correct 168 ms 25856 KB Output is correct
12 Incorrect 28 ms 5444 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4948 KB Output is correct
2 Correct 45 ms 6272 KB Output is correct
3 Correct 43 ms 6400 KB Output is correct
4 Correct 47 ms 6400 KB Output is correct
5 Correct 39 ms 6764 KB Output is correct
6 Correct 41 ms 6396 KB Output is correct
7 Correct 37 ms 5620 KB Output is correct
8 Correct 116 ms 20872 KB Output is correct
9 Correct 112 ms 20752 KB Output is correct
10 Correct 31 ms 5428 KB Output is correct
11 Correct 136 ms 31048 KB Output is correct
12 Correct 119 ms 31008 KB Output is correct
13 Correct 112 ms 31080 KB Output is correct
14 Correct 33 ms 5436 KB Output is correct
15 Correct 107 ms 20708 KB Output is correct
16 Correct 114 ms 21196 KB Output is correct
17 Correct 184 ms 21604 KB Output is correct
18 Correct 129 ms 21628 KB Output is correct
19 Correct 146 ms 26812 KB Output is correct
20 Correct 167 ms 25852 KB Output is correct
21 Correct 124 ms 20712 KB Output is correct
22 Correct 116 ms 20764 KB Output is correct
23 Correct 120 ms 21180 KB Output is correct
24 Correct 123 ms 21324 KB Output is correct
25 Correct 131 ms 23416 KB Output is correct
26 Correct 122 ms 20552 KB Output is correct
27 Correct 123 ms 20616 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4948 KB Output is correct
2 Correct 45 ms 6272 KB Output is correct
3 Correct 43 ms 6400 KB Output is correct
4 Correct 47 ms 6400 KB Output is correct
5 Correct 39 ms 6764 KB Output is correct
6 Correct 41 ms 6396 KB Output is correct
7 Correct 37 ms 5620 KB Output is correct
8 Correct 116 ms 20872 KB Output is correct
9 Correct 112 ms 20752 KB Output is correct
10 Correct 31 ms 5428 KB Output is correct
11 Correct 136 ms 31048 KB Output is correct
12 Correct 119 ms 31008 KB Output is correct
13 Correct 112 ms 31080 KB Output is correct
14 Correct 33 ms 5436 KB Output is correct
15 Correct 107 ms 20708 KB Output is correct
16 Correct 114 ms 21196 KB Output is correct
17 Correct 184 ms 21604 KB Output is correct
18 Correct 129 ms 21628 KB Output is correct
19 Correct 146 ms 26812 KB Output is correct
20 Correct 167 ms 25852 KB Output is correct
21 Correct 124 ms 20712 KB Output is correct
22 Correct 116 ms 20764 KB Output is correct
23 Correct 120 ms 21180 KB Output is correct
24 Correct 123 ms 21324 KB Output is correct
25 Correct 131 ms 23416 KB Output is correct
26 Correct 122 ms 20552 KB Output is correct
27 Correct 123 ms 20616 KB Output is correct
28 Incorrect 33 ms 5436 KB Extra information in the output file
29 Halted 0 ms 0 KB -