Submission #556760

#	Time	Username	Problem	Language	Result	Execution time	Memory
556760		MilosMilutinovic	Inside information (BOI21_servers)	C++14	50 / 100	317 ms	43592 KiB

servers

#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  vector<int> sz;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    sz.resize(n);
    iota(p.begin(), p.end(), 0);
    fill(sz.begin(), sz.end(), 1);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      if (sz[x] > sz[y]) {
        swap(x, y);
      }
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    return false;
  }
};

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];
    if (foo[i] != 'C') {
      cin >> y[i];
    }
    --x[i], --y[i];
    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];
    }
  }
  vector<int> qans(q);
  for (int i = 0; i < q; i++) {
    if (foo[i] != 'Q') {
      continue;
    }
    if (x[i] == y[i]) {
      qans[i] = 1;
      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) {
      qans[i] = 1;
    } else {
      qans[i] = 0;
    }
  }
  vector<int> ans(n, 1);
  vector<pair<int, int>> edges;
  if (n <= 4000) {
    for (int i = 0; i < q; i++) {
      if (foo[i] == 'S') {
        edges.emplace_back(x[i], y[i]);
        dsu d(n);
        vector<int> nans(n, 1);
        for (int j = edges.size() - 1; j >= 0; j--) {
          int u = edges[j].first;
          int v = edges[j].second;
          nans[u] += d.sz[d.get(v)];
          nans[v] += d.sz[d.get(u)];
          d.unite(u, v);
        }
        swap(ans, nans);
      }
      if (foo[i] == 'C') {
        qans[i] = ans[x[i]];
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (foo[i] == 'Q') {
      cout << (qans[i] == 0 ? "no" : "yes") << '\n';
    } else if (foo[i] == 'C') {
      cout << qans[i] <<  '\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