#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 120'000;
const int logn = 20;
/*int par[1 + maxn];
int sz[1 + maxn];
void make_set(int a) {
par[a] = a;
sz[a] = 1;
}
int find_set(int a) {
if(a == par[a]) {
return a;
}
return par[a] = find_set(par[a]);
}
void union_sets(int a, int b) {
a = find_set(a), b = find_set(b);
if(sz[a] < sz[b]) {
swap(a, b);
}
sz[b] += sz[a];
par[a] = b;
}*/
/*
int tree[1 + 4 * maxn];
void update(int v, int vl, int vr, int pos, int val) {
if(vl == vr) {
tree[v] = val;
return;
}
int mid = (vl + vr) / 2;
if(pos <= mid) {
update(2 * v, vl, mid, pos, val);
} else {
update(2 * v + 1, mid + 1, vr, pos, val);
}
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
int query(int v, int vl, int vr, int ql, int qr) {
if(vl > qr || vr < ql) {
return 0;
}
if(vl == ql && vr == qr) {
return tree[v];
}
int mid = (vl + vr) / 2;
return query(2 * v, vl, mid, ql, min(qr, mid)) +
query(2 * v + 1, mid + 1, vr, max(ql, mid + 1), qr);
}
*/
struct query {
int t;
int a, b;
};
int n, q;
vector<query> queries;
vector<pii > ori_graph[1 + maxn];
int par[1 + maxn];
int parwei[1 + maxn];
int depth[1 + maxn];
void dfs(int cur) {
for(pii nei : ori_graph[cur]) {
if(nei.fi != par[cur]) {
par[nei.fi] = cur;
parwei[nei.fi] = nei.se;
depth[nei.fi] = depth[cur] + 1;
dfs(nei.fi);
}
}
}
int lift[1 + maxn][logn];
int maxlift[1 + maxn][logn];
int minlift[1 + maxn][logn];
bool increase[1 + maxn][logn];
bool decrease[1 + maxn][logn];
int lca(int a, int b) {
if(depth[a] < depth[b]) {
swap(a, b);
}
for(int j = logn - 1; j >= 0; j--) {
if(depth[b] + (1 << j) <= depth[a]) {
a = lift[a][j];
}
}
for(int j = logn - 1; j >= 0; j--) {
if(lift[a][j] != lift[b][j]) {
a = lift[a][j];
b = lift[b][j];
}
}
a = lift[a][0];
b = lift[b][0];
return a; // = b
}
bool qry(int t, int a, int b) {
int c = lca(a, b);
int maxi = 0;
vector<pii > from_b, from_a;
for(int j = logn - 1; j >= 0; j--) {
if(depth[b] >= depth[c] + (1 << j)) {
if(!increase[b][j]) {
//cout << "1\n";
return false;
}
from_b.pb({minlift[b][j], maxlift[b][j]});
b = lift[b][j];
}
}
for(int j = logn - 1; j >= 0; j--) {
if(depth[a] >= depth[c] + (1 << j)) {
if(!decrease[a][j]) {
//cout << "2\n";
return false;
}
from_a.pb({minlift[a][j], maxlift[a][j]});
a = lift[a][j];
}
}
reverse(from_a.begin(), from_a.end());
for(pii p : from_a) {
from_b.pb(p);
}
for(int i = 0; i + 1 < from_b.size(); i++) {
if(from_b[i].se > from_b[i + 1].fi) {
//cout << "3\n";
return false;
}
}
if(from_b.back().se > /*maxi*/t) {
//cout << "4\n";
return false;
}
return true;
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n + q - 1; i++) {
string type;
cin >> type;
int a, b;
cin >> a >> b;
if(type == "S") {
ori_graph[a].pb({b, i});
ori_graph[b].pb({a, i});
}
if(type == "Q") {
queries.pb({i, a, b});
}
}
par[1] = 1;
dfs(1);
for(int i = 1; i <= n; i++) {
lift[i][0] = par[i];
maxlift[i][0] = minlift[i][0] = parwei[i];
increase[i][0] = decrease[i][0] = true;
}
minlift[1][0] = 3 * maxn; // thats basically infinite in this case
for(int j = 1; j < logn; j++) {
for(int i = 1; i <= n; i++) {
int between = lift[i][j - 1];
lift[i][j] = lift[between][j - 1];
maxlift[i][j] = max(maxlift[i][j - 1], maxlift[between][j - 1]);
minlift[i][j] = min(minlift[i][j - 1], minlift[between][j - 1]);
increase[i][j] = increase[i][j - 1] && increase[between][j - 1]
&& (maxlift[i][j - 1] < minlift[between][j - 1]);
decrease[i][j] = decrease[i][j - 1] && decrease[between][j - 1]
&& (minlift[i][j - 1] > maxlift[between][j - 1]);
}
}
for(query curq : queries) {
int t = curq.t, a = curq.a, b = curq.b;
cout << (qry(t, a, b) ? "yes" : "no") << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
/*
6 3
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
*/
Compilation message
servers.cpp: In function 'bool qry(int, int, int)':
servers.cpp:143:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int i = 0; i + 1 < from_b.size(); i++) {
| ~~~~~~^~~~~~~~~~~~~~~
servers.cpp:117:9: warning: unused variable 'maxi' [-Wunused-variable]
117 | int maxi = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
5000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
5000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
5072 KB |
Output is correct |
| 2 |
Runtime error |
198 ms |
90892 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
5072 KB |
Output is correct |
| 2 |
Runtime error |
198 ms |
90892 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
5044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
5044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
5072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
5072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
5044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
5044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
