Submission #556880

#	Time	Username	Problem	Language	Result	Execution time	Memory
556880		Soumya1	Inside information (BOI21_servers)	C++17	0 / 100	51 ms	5064 KiB

servers

#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
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5