#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 120069;
const int K = 18;
int up[N][K], mx[N][K], is[N][K], dd[N][K], mn[N][K];
int timer, tin[N], tout[N], dep[N], par[N];
int n, k;
vector<pair<int, int>> g[N];
string q1[N];
void dfs(int v, int p) {
tin[v] = ++timer;
dep[v] = dep[p] + 1;
up[v][0] = p;
for (int i = 1;i < K;i++) {
up[v][i] = up[up[v][i - 1]][i - 1];
mx[v][i] = max(mx[v][i - 1], mx[up[v][i - 1]][i - 1]);
mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
is[v][i] = (is[v][i - 1] && is[up[v][i - 1]][i - 1] && mx[v][i - 1] < mx[up[v][i - 1]][0]);
dd[v][i] = (dd[v][i - 1] && dd[up[v][i - 1]][i - 1] && mn[v][i - 1] > mn[up[v][i - 1]][0]);
}
for (auto u : g[v]) {
if (u.f == p)
continue;
mx[u.f][0] = mn[u.f][0] = u.s;
is[u.f][0] = dd[u.f][0] = 1;
dfs(u.f, v);
}
tout[v] = timer;
}
bool anc(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (anc(a, b))
return a;
else if (anc(b, a))
return b;
for (int i = K - 1;i >= 0;i--) {
if (!anc(up[a][i], b) && up[a][i] > 0)
a = up[a][i];
}
return up[a][0];
}
int Up(int a, int b) {
assert(anc(b, a));
int d = dep[a] - dep[b];
int r = 1;
for (int i = 0;i < K;i++) {
if (d >> i & 1) {
int t = 1;
d ^= (1 << i);
if (d > 0)
t &= (mn[a][i] < mn[up[a][i]][0]);
r &= (is[a][i] & t);
a = up[a][i];
}
}
return r;
}
int Down(int a, int b) {
assert(anc(b, a));
int d = dep[a] - dep[b];
int r = 1;
for (int i = 0;i < K;i++) {
if (d >> i & 1) {
int t = 1;
d ^= (1 << i);
if (d > 0)
t &= (mx[a][i] > mx[up[a][i]][0]);
r &= (dd[a][i] & t);
a = up[a][i];
}
}
return r;
}
int Mx(int a, int b) {
assert(anc(b, a));
int d = dep[a] - dep[b];
int r = 0;
for (int i = 0;i < K;i++) {
if (d >> i & 1) {
r = max(r, mx[a][i]);
a = up[a][i];
}
}
return r;
}
int Mn(int a, int b) {
assert(anc(b, a));
int d = dep[a] - dep[b];
int r = 1e9;
for (int i = 0;i < K;i++) {
if (d >> i & 1) {
r = min(r, mn[a][i]);
a = up[a][i];
}
}
return r;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n >> k;
vector<tuple<int, int, int>> qs;
for (int i = 1;i <= n - 1 + k;i++) {
char c;
cin >> c;
int a, b;
if (c == 'S') {
cin >> a >> b;
g[a].push_back({b, i});
g[b].push_back({a, i});
}
else if (c == 'Q') {
cin >> a >> b;
qs.push_back({a, b, i});
}
else {
cin >> a;
qs.push_back({a, -1, i});
}
}
dfs(1, 0);
for (auto j : qs) {
int a, b, c;
tie(a, b, c) = j;
if (b == -1) {
assert(false);
cout << "0\n";
}
else {
int lc = lca(a, b);
//od b od lc rastuce
int mx1 = Mx(b, lc);
int mx2 = Mx(a, lc);
int mn1 = Mn(b, lc);
int mm = max(mx1, mx2);
bool ok = (Up(b, lc) && Down(a, lc) && c > mm && mn1 > mm);
cout << (ok ? "yes" : "no") << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
12752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
12752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
12620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
12620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
12740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
12740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
12608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
12608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
