Submission #1139487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139487		Mamedov	Inside information (BOI21_servers)	C++20	100 / 100	634 ms	137304 KiB

servers

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
#define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


template <typename T> void show(vector<T> &v) {
  for (T i : v) {
    cout << i << ' ';
  }
  cout << ln;
}

template <typename T> struct implicitSegTree {
  int nextFree, n;
  vector<T>tree;
  vi L, R;
  implicitSegTree(int _n) {
    nextFree = 1;
    n = _n;
    tree.assign(2, 0);
    L.assign(2, 0);
    R.assign(2, 0);
  }
  void createNode() {
    tree.eb(0);
    L.eb(0);
    R.eb(0);
    ++nextFree;
  }
  void upd(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
      tree[v] += val;
    } else {
      int mid = (tl + tr) >> 1;
      if (pos <= mid) {
        if (!L[v]) {
          createNode();
          L[v] = nextFree;
        }
        upd(L[v], tl, mid, pos, val);
      } else {
        if (!R[v]) {
          createNode();
          R[v] = nextFree;
        }
        upd(R[v], mid + 1, tr, pos, val);
      }
      tree[v] = tree[L[v]] + tree[R[v]];
    }
  }
  void upd(int pos, int val) {
    upd(1, 1, n, pos, val);
  }
  T get(int v, int tl, int tr, int ql, int qr) {
    if (tr < ql || qr < tl) return 0;
    if (ql <= tl && tr <= qr) return tree[v];
    int mid = (tl + tr) >> 1;
    T lSum = get(L[v], tl, mid, ql, qr);
    T rSum = get(R[v], mid + 1, tr, ql, qr);
    return lSum + rSum;
  }
  T sum(int l, int r) {
    return get(1, 1, n, l, r);
  }
};

struct CentroidDecomposition {
  vector<vector<array<int, 2>>>g;
  vector<bool>removed;
  vector<int>subSize;
  vector<vector<int>>cents;
  vector<implicitSegTree<int>>incFromCent;
  vector<vector<array<int, 2>>>events;
  vector<vector<array<int, 2>>>incToCentFrom;
  vector<vector<array<int, 3>>>decToCentFrom;
  int maxID;
  int lastEventID;
  CentroidDecomposition(int n, int k, vector<array<int, 3>> &e) {
    maxID = n + k;
    g.resize(n + 1);
    for (auto [u, v, w] : e) {
      g[u].pb({v, w});
      g[v].pb({u, w});
    }
    removed.assign(n + 1, false);
    subSize.resize(n + 1);
    cents.resize(n + 1);
    incFromCent.assign(n + 1, implicitSegTree<int>(maxID));
    incToCentFrom.resize(n + 1);
    decToCentFrom.resize(n + 1);
    events.resize(maxID);
    lastEventID = 0;
  }
  int getSubSize(int v, int pa = -1) {
    subSize[v] = 1;
    for (auto [to, w] : g[v]) {
      if (to != pa && !removed[to]) subSize[v] += getSubSize(to, v);
    }
    return subSize[v];
  }
  int findCentroid(int v, int halfSize, int pa = -1) {
    for (auto [to, w] : g[v]) {
      if (to != pa && !removed[to] && subSize[to] > halfSize) return findCentroid(to, halfSize, v);
    }
    return v;
  }
  void getIncPaths(int v, int centroid, int centW, int pa, int prevW, bool isInc, bool isDec) {
    cents[v].pb(centroid);
    if (isInc) {
      events[prevW].pb({centroid, centW});
      decToCentFrom[v].pb({centroid, centW, prevW});
    }
    if (isDec) {
      incToCentFrom[v].pb({centroid, centW});
    }
    for (auto [to, w] : g[v]) {
      if (to != pa && !removed[to]) {
        if (isInc && w > prevW) getIncPaths(to, centroid, centW, v, w, true, false);
        else if (isDec && w < prevW) getIncPaths(to, centroid, centW, v, w, false, true);
        else getIncPaths(to, centroid, centW, v, w, false, false);
      }
    }
  }
  int build(int v = 1) {
    int centroid = findCentroid(v, getSubSize(v) >> 1);
    removed[centroid] = true;
    cents[centroid].pb(centroid);
    incToCentFrom[centroid].pb({centroid, 0}); // for paths starting at centroid
    for (auto [to, w] : g[centroid]) {
      if (!removed[to]) getIncPaths(to, centroid, w, centroid, w, true, true);
    }
    for (auto [to, w] : g[centroid]) {
      if (!removed[to]) build(to);
    }
    return centroid;
  }
  void updateEvents(int id) {
    for (int i = lastEventID + 1; i < id; ++i) {
      for (auto [centroid, w] : events[i]) {
        incFromCent[centroid].upd(w, 1);
      }
    }
    lastEventID = id;
  }
  int count(int d, int id) {
    updateEvents(id);
    int res = 0;
    for (auto [centroid, w] : incToCentFrom[d]) {
      if (w < id) {
        res++;
        res += incFromCent[centroid].sum(w + 1, id);
      }
    }
    return res;
  }
  string ask(int a, int d, int id) {
    if (a == d) return "yes";
    int cent = -1;
    int mn = min((int)cents[d].size(), (int)cents[a].size());
    for (int i = 0; i < mn; ++i) {
      if (cents[d][i] == cents[a][i]) cent = cents[d][i];
      else break;
    }
    int wd = oo;
    for (auto [centroid, w] : incToCentFrom[d]) {
      if (centroid == cent) {
        wd = w;
        break;
      }
    }
    if (cent == a && wd < id) return "yes";

    int wla = oo, wra = oo;
    for (auto [centroid, wl, wr] : decToCentFrom[a]) {
      if (centroid == cent) {
        wla = wl;
        wra = wr;
        break;
      }
    }
    if (wla > wd && wra < id) return "yes";
    else return "no";
  }
};

void solve() {
  int n, k;
  cin >> n >> k;
  
  vector<array<int, 3>>e;
  vector<array<int, 3>>qrs;
  for (int i = 1; i < n + k; ++i) {
    char type;
    int u, v = -1;
    cin >> type >> u;
    if (type != 'C') cin >> v;
    
    if (type == 'S') {
      e.pb({u, v, i});
    } else {
      qrs.pb({u, v, i});
    }
  }
  CentroidDecomposition cd(n, k, e);
  cd.build();

  for (auto [u, v, id] : qrs) {
    if (v == -1) {
      cout << cd.count(u, id) << ln;
    } else {
      cout << cd.ask(u, v, id) << ln;
    }
  }
}
int main() {
  iospeed;
  solve();
  return 0;
}

• Subtask 1-1: 2 / 2
• Subtask 1-2: 3 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 5 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 10 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 13 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 18 / 18