#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1.2e5 + 11;
const int LGN = 17;
vector<pair<int, int>> G[MAXN];
int isq[MAXN * 2], ans[MAXN * 2];
void share(int a, int b, int t){
G[a].push_back({b, t});
G[b].push_back({a, t});
}
int p[MAXN], anc[LGN][MAXN];
bool _inc[LGN][MAXN], _dec[LGN][MAXN];
int _max[LGN][MAXN], _min[LGN][MAXN];
int c[MAXN], dep[MAXN];
void dfs(int v, int pa = -1){
if(pa == -1){
p[v] = anc[0][v] = v; for(int j = 1; j < LGN; j++) anc[j][v] = v;
}
for(auto [u, t] : G[v]){
if(u != pa){
p[u] = anc[0][u] = v; for(int j = 1; j < LGN; j++) anc[j][u] = anc[j - 1][anc[j - 1][u]];
dep[u] = dep[v] + 1; _max[0][u] = _min[0][u] = t; _inc[0][u] = _dec[0][u] = true; c[u] = t;
for(int j = 1; j < LGN; j++){
_max[j][u] = max(_max[j - 1][u], _max[j - 1][anc[j - 1][u]]);
_min[j][u] = min(_min[j - 1][u], _min[j - 1][anc[j - 1][u]]);
_inc[j][u] = _inc[j - 1][u] && _inc[j - 1][anc[j - 1][u]] && _max[j - 1][u] <= _min[j - 1][anc[j - 1][u]];
_dec[j][u] = _dec[j - 1][u] && _dec[j - 1][anc[j - 1][u]] && _min[j - 1][u] >= _max[j - 1][anc[j - 1][u]];
}
dfs(u, v);
}
}
}
int kth_anc(int u, int k){
for(int j = LGN - 1; j >= 0; j--){
if(k & (1 << j)) u = anc[j][u];
}
return u;
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
u = kth_anc(u, dep[u] - dep[v]);
for(int j = LGN - 1; j >= 0; j--){
if(anc[j][u] != anc[j][v])
u = anc[j][u], v = anc[j][v];
}
return u == v ? u : p[u];
}
bool is_inc(int u, int l){
int diff = dep[u] - dep[l];
int d = __lg(diff);
return _inc[d][u] && _inc[d][kth_anc(u, diff - (1 << d))];
}
bool is_dec(int u, int l){
int diff = dep[u] - dep[l];
int d = __lg(diff);
return _dec[d][u] && _dec[d][kth_anc(u, diff - (1 << d))];
}
struct query_1{
int a, d, t;
};
struct query_2{
int d, t;
};
vector<query_1> Q1;
vector<query_2> Q2;
void query(int a, int d, int t){
Q1.push_back({a, d, t});
}
void count(int d, int t){
Q2.push_back({d, t});
}
int32_t main(){
int n, k; cin >> n >> k;
for(int t = 0; t < n + k - 1; t++){
char c; cin >> c;
if(c == 'S'){
int a, b; cin >> a >> b;
share(a, b, t);
}else if(c == 'Q'){
int a, d; cin >> a >> d;
query(a, d, t);
isq[t] = 1;
}else{
int d; cin >> d;
count(d, t);
isq[t] = 2;
}
}
dfs(1);
for(auto [a, d, t] : Q1){
if(a == d){
ans[t] = true;
continue;
}
int l = lca(a, d);
ans[t] = true;
if(l == a){
ans[t] = is_inc(d, l);
ans[t] &= c[kth_anc(d, dep[a] - dep[d] - 1)] <= t;
}else if(l == d){
ans[t] = is_dec(a, l);
ans[t] &= c[a] <= t;
}else{
ans[t] = is_inc(d, l);
ans[t] &= is_dec(a, l);
ans[t] &= c[kth_anc(a, dep[a] - dep[l] - 1)] >= c[kth_anc(d, dep[d] - dep[l] - 1)];
ans[t] &= c[a] <= t;
}
}
for(int t = 0; t < n + k - 1; t++){
if(isq[t] == 1){
cout << (ans[t] ? "yes" : "no") << endl;
}else if(isq[t] == 2){
cout << ans[t] << endl;
}
}
}
Compilation message
servers.cpp: In function 'void dfs(int, int)':
servers.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | for(auto [u, t] : G[v]){
| ^
servers.cpp: In function 'int32_t main()':
servers.cpp:104:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
104 | for(auto [a, d, t] : Q1){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
7228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
178 ms |
7228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
7192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
7192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
7200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
7200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
7180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
7180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
162 ms |
7260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
7176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
7176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
