/*
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";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
2116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
2116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
2124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
2124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
2112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
2112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
2108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
2108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
2096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
2096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
