oj.uz

Submission #556880

# Submission time Handle Problem Language Result Execution time Memory
556880 2022-05-04T09:04:05 Z Soumya1 Inside information (BOI21_servers) C++17
0 / 100
 51 ms 5064 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
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 5028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 4988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 4988 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 5064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 5064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 5060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 5052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 5052 KB Output isn't correct
2 Halted 0 ms 0 KB -