제출 #666764

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

servers

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  q += n - 1;
  vector<vector<pair<int, int>>> g(n);
  vector<char> op(q);
  vector<int> x(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    string foo;
    cin >> foo;
    op[i] = foo[0];
    if (op[i] == 'S') {
      cin >> x[i] >> y[i];
      --x[i]; --y[i];
      g[x[i]].emplace_back(y[i], i);
      g[y[i]].emplace_back(x[i], i);
    }
    if (op[i] == 'Q') {
      cin >> x[i] >> y[i];
      --x[i]; --y[i];
    }
    if (op[i] == 'C') {
      cin >> x[i];
      --x[i];
    }
  }
  vector<vector<int>> qs(n);
  for (int i = 0; i < q; i++) {
    if (op[i] == 'C') {
      qs[x[i]].push_back(i);
    }
  }
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), [&](pair<int, int> a, pair<int, int> b) {
      return a.second > b.second;
    });
  }
  vector<bool> was(n);
  vector<int> sz(n);
  function<void(int, int)> Find_sz = [&](int v, int pv) {
    sz[v] = 1;
    for (auto& p : g[v]) {
      int to = p.first;
      if (!was[to] && to != pv) {
        Find_sz(to, v);
        sz[v] += sz[to];
      }
    }
  };
  function<int(int, int, int)> Find_cen = [&](int v, int pv, int n) {
    for (auto& p : g[v]) {
      int to = p.first;
      if (!was[to] && to != pv && sz[to] * 2 >= n) {
        return Find_cen(to, v, n);
      }
    }
    return v;
  };
  vector<int> qv;
  vector<int> fenw(q + 1);
  auto Modify = [&](int x, int v) {
    for (x++; x <= q; x += x & -x) {
      fenw[x] += v;
    }
  };
  auto Query = [&](int x) {
    int r = 0;
    for (x++; x > 0; x -= x & -x) {
      r += fenw[x];
    }
    return r;
  };
  vector<int> ans(q);
  function<void(int, int, int, int, bool, bool)> Go = [&](int v, int pv, int prv_w, int fir, bool inc, bool dec) {
    if (dec) {
      for (auto& p : qs[v]) {
        ans[p] += Query(p) + (fir <= p);
      }
    }
    if (inc) {
      qv.push_back(prv_w);
    }
    for (auto& p : g[v]) {
      int to = p.first;
      int w = p.second;
      if (!was[to] && to != pv) {
        Go(to, v, w, fir, (inc & (w > prv_w)), (dec & (w < prv_w)));
      }
    }
  };
  function<void(int, int)> Decompose = [&](int v, int pv) {
    Find_sz(v, v);
    v = Find_cen(v, v, sz[v]);
    was[v] = true;
    vector<int> rv;
    for (auto& p : g[v]) {
      int to = p.first;
      int w = p.second;
      if (!was[to]) {
        Go(to, v, w, w, 1, 1);
        for (auto& p : qv) {
          Modify(p, +1);
          rv.push_back(p);
        }
        qv.clear();
      }
    }   
    for (auto& p : qs[v]) {
      ans[p] += Query(p);
    }
    for (auto& p : rv) {
      Modify(p, -1);
    }
    for (auto& p : g[v]) {
      int to = p.first;
      if (!was[to] && to != pv) {
        Decompose(to, v);
      }
    }
  };
  Decompose(0, -1);
  const int L = 20;
  vector<int> inc_up(n);
  vector<int> dec_up(n);
  vector<int> dep(n);
  vector<int> up(n);
  vector<vector<int>> pr(L, vector<int>(n));
  function<void(int, int, int)> Dfs = [&](int v, int pv, int prv_w) {
    pr[0][v] = pv;
    up[v] = prv_w;
    for (auto& p : g[v]) {
      int to = p.first;
      int w = p.second;
      if (to == pv) {
        continue;
      }
      dep[to] = dep[v] + 1;
      if (prv_w == -1) {
        inc_up[to] = 0;
        dec_up[to] = 0;        
      } else if (prv_w > w) {
        inc_up[to] = inc_up[v];
        dec_up[to] = dep[v];
      } else {
        inc_up[to] = dep[v];
        dec_up[to] = dec_up[v];
      }
      Dfs(to, v, w);
    }
  };
  Dfs(0, 0, -1);
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      pr[j][i] = pr[j - 1][pr[j - 1][i]];
    }
  }
  auto LCA = [&](int x, int y) {
    if (dep[x] < dep[y]) {
      swap(x, y);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[pr[i][x]] >= dep[y]) {
        x = pr[i][x];
      }
    }
    if (x == y) {
      return x;
    }    
    for (int i = L - 1; i >= 0; i--) {
      if (pr[i][x] != pr[i][y]) {
        x = pr[i][x];
        y = pr[i][y];
      }
    }
    return pr[0][x];
  };
  auto GoUp = [&](int x, int k) {
    for (int i = L - 1; i >= 0; i--) {
      if (k >> i & 1) {
        x = pr[i][x];
      }
    }
    return x;
  };
  for (int i = 0; i < q; i++) {
    if (op[i] == 'Q') {
      swap(x[i], y[i]);
      int lca = LCA(x[i], y[i]);
      bool is_inc = (inc_up[x[i]] <= dep[lca] && dec_up[y[i]] <= dep[lca]);
      is_inc = (is_inc & (x[i] == lca || y[i] == lca || up[GoUp(x[i], dep[x[i]] - dep[lca] - 1)] < up[GoUp(y[i], dep[y[i]] - dep[lca] - 1)]));
      if (x[i] != lca) {
        is_inc = (is_inc && up[GoUp(x[i], dep[x[i]] - dep[lca] - 1)] < i);
      }
      if (y[i] != lca) {
        is_inc = (is_inc && up[y[i]] < i);
      }
      cout << (is_inc ? "yes" : "no") << '\n';
    }
    if (op[i] == 'C') {
      cout << ans[i] + 1 << '\n';
    }
  }
  return 0;
}

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