Submission #1139459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139459		Mamedov	Inside information (BOI21_servers)	C++20	51 / 100	290 ms	96824 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;
}

struct CentroidDecomposition {
  vector<vector<array<int, 2>>>g;
  vector<bool>removed;
  vector<int>subSize;
  vector<vector<int>>cents;
  vector<vector<int>>incFromCent, incFromCentChild;
  vector<vector<array<int, 3>>>incToCentFrom, decToCentFrom;
  int nxt = 0;
  CentroidDecomposition(int n, vector<array<int, 3>> &e) {
    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.resize(n + 1);
    incToCentFrom.resize(n + 1);
    decToCentFrom.resize(n + 1);
  }
  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) {
      //incFromCent[centroid].pb(prevW);
      incFromCentChild[nxt].pb(prevW);
      decToCentFrom[v].pb({centroid, centW, prevW});
    }
    if (isDec) {
      incToCentFrom[v].pb({centroid, nxt, 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, -1, 0}); // for paths starting at centroid
    for (auto [to, w] : g[centroid]) {
      if (!removed[to]) {
        incFromCentChild.pb({});
        getIncPaths(to, centroid, w, centroid, w, true, true);
        sort(all(incFromCentChild[nxt]));
        incFromCent[centroid].insert(incFromCent[centroid].end(), all(incFromCentChild[nxt]));
        nxt++;
      }
    }
    sort(all(incFromCent[centroid]));
    for (auto [to, w] : g[centroid]) {
      if (!removed[to]) build(to);
    }
    return centroid;
  }
  int count(int d, int id) {
    int res = 1;
    for (auto [centroid, centChild, w] : incToCentFrom[d]) {
      if (w < id) {
        //res++;
        res += (upper_bound(all(incFromCent[centroid]), id) - lower_bound(all(incFromCent[centroid]), w));
        if (centChild != -1) res -= (upper_bound(all(incFromCentChild[centChild]), id) - upper_bound(all(incFromCentChild[centChild]), w));
      }
    }
    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, centChild, 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, 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: 0 / 3
• Subtask 2-1: 2 / 2
• Subtask 2-2: 3 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 10 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 12 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 17 / 17
• Subtask 6-2: 0 / 18