제출 #556740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
556740		MilosMilutinovic	Inside information (BOI21_servers)	C++14	50 / 100	367 ms	41784 KiB

servers

#include <bits/stdc++.h>

using namespace std;

int main() {
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<vector<pair<int, int>>> g(n);
  int q = n - 1 + k;
  vector<char> foo(q);
  vector<int> x(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    cin >> foo[i] >> x[i] >> y[i];
    --x[i], --y[i];
    assert(x[i] >= 0 && x[i] < n && y[i] >= 0 && y[i] < n);
    if (foo[i] == 'S') {
      g[x[i]].emplace_back(y[i], i);
      g[y[i]].emplace_back(x[i], i);
    }
  }
  vector<int> par(n);
  vector<int> wei(n);
  vector<int> dep(n);
  function<void(int, int)> Dfs = [&](int u, int pr) {
    dep[u] = dep[pr] + 1;
    for (auto& e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (v == pr) {
        continue;
      }
      par[v] = u;
      wei[v] = w;
      Dfs(v, u);
    }
  };
  Dfs(0, 0);
  wei[0] = 1000000;
  const int L = 20;
  vector<vector<int>> up(n, vector<int>(L));
  for (int i = 0; i < n; i++) {
    up[i][0] = par[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      up[i][j] = up[up[i][j - 1]][j - 1];
    }
  }
  auto Lca = [&](int u, int v) {
    if (dep[u] < dep[v]) {
      swap(u, v);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[up[u][i]] >= dep[v]) {
        u = up[u][i];
      }
    }
    if (u == v) {
      return u;
    }
    for (int i = L - 1; i >= 0; i--) {
      if (up[u][i] != up[v][i]) {
        u = up[u][i];
        v = up[v][i];
      }
    }
    return up[u][0];
  };
  auto Lift = [&](int x, int d) {
    for (int i = L - 1; i >= 0; i--) {
      if (d >> i & 1) {
        x = up[x][i];
      }
    }
    return x;
  };
  vector<vector<int>> go(n, vector<int>(2, 0));
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return dep[i] < dep[j];
  });
  for (int id = 1; id < n; id++) {
    int i = order[id];
    if (wei[par[i]] > wei[i]) {
      go[i][0] = go[par[i]][0];
      go[i][1] = par[i];
    } else {
      go[i][0] = par[i];
      go[i][1] = go[par[i]][1];
    }
  }
  for (int i = 0; i < q; i++) {
    if (foo[i] != 'Q') {
      continue;
    }
    if (x[i] == y[i]) {
      cout << "yes" << '\n';
      continue;
    }
    int z = Lca(x[i], y[i]);
    bool ok = true;
    if (x[i] != z && y[i] != z) {
      int p_x = Lift(x[i], dep[x[i]] - dep[z] - 1);
      int p_y = Lift(y[i], dep[y[i]] - dep[z] - 1);
      if (wei[p_y] > wei[p_x]) {
        ok = false;
      }
    }
    if (x[i] != z && wei[x[i]] > i) {
      ok = false;
    }
    if (y[i] != z && wei[Lift(y[i], dep[y[i]] - dep[z] - 1)] > i) {
      ok = false;
    }
    if (dep[go[y[i]][0]] <= dep[z] && dep[go[x[i]][1]] <= dep[z] && ok) {
      cout << "yes" << '\n';
    } else {
      cout << "no" << '\n';
    }
  }
  return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5