#include <iostream>
#include <vector>
using namespace std;
struct way {
int mnt;
int mxt;
bool incr = true;
bool dcr = true;
way() {}
way(int t): mnt(t), mxt(t) {}
way reverse() {
way ans;
ans.mnt = mnt;
ans.mxt = mxt;
ans.dcr = incr;
ans.incr = dcr;
return ans;
}
way operator+(way w) {
way ans;
ans.mnt = min(mnt, w.mnt);
ans.mxt = max(mxt, w.mxt);
ans.incr = (incr && w.incr && mxt <= w.mnt);
ans.dcr = (dcr && w.dcr && mnt >= w.mxt);
return ans;
}
};
const int MAXN = 120008;
vector<pair<int, int>> edg[MAXN];
int depth[MAXN];
pair<int, int> rt[MAXN];
pair<int, way> crt[MAXN];
void dfs(int v) {
auto [rtv, tmv] = rt[v];
int par = crt[rtv].first;
int parpar = crt[par].first;
if (depth[rtv] - depth[par] == depth[par] - depth[parpar]) {
crt[v] = {parpar, way(tmv) + crt[rtv].second + crt[par].second};
} else {
crt[v] = {rtv, way(tmv)};
}
for (auto [u, t] : edg[v]) {
if (u == rtv)
continue;
rt[u] = {v, t};
depth[u] = depth[v] + 1;
dfs(u);
}
}
pair<int, way> lift(int v, int d) {
way ans = rt[v].second;
while (d) {
if (depth[v] - depth[crt[v].first] <= d) {
ans = ans + crt[v].second;
d -= depth[v] - depth[crt[v].first];
v = crt[v].first;
} else {
ans = ans + rt[v].second;
--d;
v = rt[v].first;
}
}
return {v, ans};
}
pair<int, pair<way, way>> lca(int v, int u) {
way ansv = rt[v].second;
way ansu = rt[u].second;
if (depth[v] > depth[u]) {
pair<int, way> vlift = lift(v, depth[v] - depth[u]);
ansv = ansv + vlift.second;
v = vlift.first;
} else if (depth[v] < depth[u]) {
pair<int, way> ulift = lift(u, depth[u] - depth[v]);
ansu = ansu + ulift.second;
u = ulift.first;
}
while (u != v) {
if (crt[v].first != crt[u].first) {
ansv = ansv + crt[v].second;
ansu = ansu + crt[u].second;
v = crt[v].first;
u = crt[u].first;
} else {
ansv = ansv + rt[v].second;
ansu = ansu + rt[u].second;
v = rt[v].first;
u = rt[u].first;
}
}
return {v, {ansv, ansu}};
}
signed main() {
int n, k;
cin >> n >> k;
vector<pair<int, pair<int, int>>> qrs;
for (int i = 0; i < n + k - 1; ++i) {
char ch;
cin >> ch;
if (ch == 'S') {
int u, v;
cin >> u >> v;
--u, --v;
edg[u].push_back({v, i});
edg[v].push_back({u, i});
} else if (ch == 'Q') {
int u, v;
cin >> u >> v;
--u, --v;
qrs.push_back({i, {v, u}});
} else {
int v;
cin >> v;
--v;
qrs.push_back({i, {v, -1}});
}
}
dfs(0);
for (int i = 0; i < k; ++i) {
auto [t, qri] = qrs[i];
auto [v, u] = qri;
if (u == -1) {
} else {
auto ans = lca(v, u);
way w = ans.second.first + ans.second.second.reverse();
if (w.incr && w.mxt <= t) {
cout << "yes\n";
} else {
cout << "no\n";
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
7780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
7780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
7704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
7704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
7816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
7816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
7748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
7748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
7720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
7720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
