제출 #550210

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550210		lorenzoferrari	Inside information (BOI21_servers)	C++17	0 / 100	79 ms	2140 KiB

servers

/*

for each server v, define f(v, t) as the number of servers
reachable from v using share operations with timestamp >= t

each node v has deg(v) "interesting" values t, its edges
\sum_{v=0}^{n}{ deg(v) } = O(n)

f(v, t) = f(v, max tt <= t s.t. tt is "interesting", or 0 if no such tt exists)

f(v, t) = 1 (me) + \sum_{u,w \in adj[v]}{ f(u, w+1) }

answer query "count how many have a": return f(a, 0)

answer query "does a have b": LCA, is path a->b strictly increasing
*/

#include <bits/stdc++.h>
using namespace std;

struct nd {
  int v, tin, tout, max;
  bool inc, dec;
  nd() {}
  nd(int v, int t = -1) : v(v), tin(t), tout(t), max(t), inc(true), dec(true) {}
};
nd join(const nd& a, const nd& b) {
  nd ans;
  ans.v = b.v;
  ans.tin = a.tin != -1 ? a.tin : b.tin;
  ans.tout = b.tout != -1 ? b.tout : a.tout;
  ans.max = max(a.max, b.max);
  ans.inc = a.inc && b.inc && (a.tin == -1 || b.tin == -1 || a.tout < b.tin);
  ans.dec = a.dec && b.dec && (a.tin == -1 || b.tin == -1 || a.tout > b.tin);
  return ans;
}

struct Lca {
  const int LOG = 18;
  int n;
  vector<int> dep;
  vector<vector<nd>> up;
  Lca(int n, vector<int> par, vector<int> dep, vector<int> tim) : n(n), dep(dep) {
    up.assign(n, vector<nd>(LOG));
    for (int i = 0; i < n; ++i) up[i][0] = nd(par[i], tim[i]);
    for (int i = 1; i < LOG; ++i) {
      for (int j = 0; j < n; ++j) {
        up[j][i] = join(up[j][i-1], up[up[j][i-1].v][i-1]);
      }
    }
  }
  nd lift(nd v, int k) {
    for (int i = LOG-1; i >= 0; --i) {
      if (k >= (1 << i)) {
        k -= (1 << i);
        v = join(v, up[v.v][i]);
      }
    }
    return v;
  }
  bool good(int a, int b, int t) {
    // return wheher path a->b is strictly increasing and with timestamp <= t
    nd na(a); na = lift(na, dep[a] - dep[b]);
    nd nb(b); nb = lift(nb, dep[b] - dep[a]);
    for (int i = LOG-1; i >= 0; --i) {
      if (up[na.v][i].v != up[nb.v][i].v) {
        na = join(na, up[na.v][i]);
        nb = join(nb, up[nb.v][i]);
      }
    }
    if (na.v != nb.v) {
      na = lift(na, 1);
      nb = lift(nb, 1);
    }
    return na.inc && nb.dec && na.tout < nb.tout && max(na.max, nb.max) <= t;
  }
};

int main() {
#ifdef LORENZO
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  int n; cin >> n;
  int k; cin >> k;
  vector<array<int, 3>> qs;
  vector<vector<array<int, 2>>> adj(n);
  for (int i = 0; i < n-1+k; ++i) {
    char c; cin >> c;
    if (c == 'S') {
      int a, b; cin >> a >> b; --a; --b;
      adj[a].push_back({b, i});
      adj[b].push_back({a, i});
    } else if (c == 'Q') {
      int a, d; cin >> a >> d; --a; --d;
      qs.push_back({a, d, i});
    } else if (c == 'C') {
      int d; cin >> d; --d;
      qs.push_back({d, -1, i});
    }
  }
  vector<int> par(n, 0), dep(n, 0), tim(n, -1);
  auto dfs = [&](auto&& self, int v) -> void {
    for (auto& [u, t] : adj[v]) {
      if (u == par[v]) continue;
      par[u] = v;
      tim[u] = t;
      dep[u] = dep[v] + 1;
      self(self, u);
    }
  };
  dfs(dfs, 0);
  Lca lca(n, par, dep, tim);
  for (auto [a, b, t] : qs) {
    if (b != -1) {
      cout << (lca.good(b, a, t) ? "yes" : "no") << "\n";
    } else {
      cout << 42 << "\n";
    }
  }
}

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