#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 25;
const int B = 18;
int n, q;
array <int, 4> queries[MAXN];
vector <pair <int, int>> adj[MAXN];
int p[MAXN], dp[B][MAXN], dep[MAXN], top[B][MAXN], inc[B][MAXN], decr[B][MAXN];
void dfs (int pos, int par) {
p[pos] = par;
for (auto [j, k] : adj[pos]) {
if (j == par) continue;
dep[j] = 1 + dep[pos];
dp[0][j] = pos;
top[0][j] = k;
inc[0][j] = 1;
decr[0][j] = 1;
for (int i = 1; i < B; i++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
top[i][j] = top[i - 1][dp[i - 1][j]];
inc[i][j] = inc[i - 1][j] && inc[i - 1][dp[i - 1][j]] && (top[i - 1][j] <= top[0][dp[i - 1][j]]);
decr[i][j] = decr[i - 1][j] && decr[i - 1][dp[i - 1][j]] && (top[i - 1][j] >= top[0][dp[i - 1][j]]);
}
dfs(j, pos);
}
}
int jump (int a, int b) {
for (int i = B - 1; i >= 0; i--) {
if (b & (1 << i)) {
a = dp[i][a];
}
}
return a;
}
int lca (int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
b = jump(b, dep[b] - dep[a]);
if (a == b) return a;
for (int i = B - 1; i >= 0; i--) {
int x = dp[i][a], y = dp[i][b];
if (x && y && x != y) {
a = x, b = y;
}
}
return dp[0][a];
}
pair <bool, int> check_inc (int a, int b, int x) {
bool f = 1; int last = 0;
for (int i = B - 1; i >= 0; i--) {
int z = dp[i][a];
if (!z || dep[z] <= dep[b]) continue;
f &= inc[i][a]; f &= top[0][a] >= last;
last = top[i][a]; a = z;
}
f &= top[0][a] <= x;
f &= top[0][a] >= last;
return {f, top[0][a]};
}
pair <bool, int> check_decr (int a, int b, int x) {
bool f = top[0][a] <= x; int last = 1e9;
for (int i = B - 1; i >= 0; i--) {
int z = dp[i][a];
if (!z || dep[z] <= dep[b]) continue;
f &= decr[i][a]; f &= top[0][a] <= last;
last = top[i][a]; a = z;
}
f &= top[0][a] <= last;
return {f, top[0][a]};
}
bool check (int a, int b, int x) {
if (a == b) return 1;
int z = lca(a, b);
if (z == a) return check_decr(b, z, x).first;
if (z == b) return check_inc(a, z, x).first;
auto g = check_inc(a, z, x), h = check_decr(b, z, x);
return g.first && h.first && g.second <= h.second;
}
void solve () {
cin >> n >> q;
int ee = 0;
for (int i = 1; i <= n - 1 + q; i++) {
char c; cin >> c;
if (c == 'S') {
int x, y; cin >> x >> y;
adj[x].push_back({y, i});
adj[y].push_back({x, i});
} else if (c == 'Q') {
int x, y; cin >> x >> y;
queries[++ee] = {1, y, x, i};
} else {
int x; cin >> x;
queries[++ee] = {2, x, 0, i};
}
}
dfs(1, 0);
for (int i = 1; i <= q; i++) {
auto g = check(queries[i][1], queries[i][2], queries[i][3]);
cout << (g ? "yes\n" : "no\n");
}
}
signed main () {
#ifndef ONLINE_JUDGE
freopen("input_file", "r", stdin);
//freopen("output_file", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
int tc = 1; //cin >> tc;
while (tc--) solve();
}
Compilation message
servers.cpp: In function 'void dfs(int, int)':
servers.cpp:11:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
11 | for (auto [j, k] : adj[pos]) {
| ^
servers.cpp: In function 'int main()':
servers.cpp:103:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | freopen("input_file", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
10584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
