#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120005;
const int MM = 17;
vector <pair <int, int>> adj[MAXN];
pair <int, int> queries[MAXN];
int t[MAXN];
int cnt = 0;
vector <int> pp[MAXN];
int dp[MM][MAXN];
int inc[MM][MAXN];
int decc[MM][MAXN];
int mx[MM][MAXN];
int top[MM][MAXN];
int u[MAXN];
int dep[MAXN];
void calc (int pos, int par) {
for (auto j : adj[pos]) {
if (j.first != par) {
dep[j.first] = 1 + dep[pos];
dp[0][j.first] = pos;
inc[0][j.first] = 1;
decc[0][j.first] = 1;
mx[0][j.first] = top[0][j.first] = j.second;
u[j.first] = j.second;
calc(j.first, pos);
}
}
}
int jump (int a, int b) {
for (int i = MM - 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 = MM - 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];
}
bool checkinc (int a, int x) { //increasing upwards
if (a == x) return 1;
int e = dep[a] - dep[x];
//cout << a << " | " << x << '\n';
//cout << e << " dd\n";
int last = 0;
for (int i = MM - 1; i >= 0; i--) {
if (e & (1 << i)) {
if (u[a] < last) return 0;
if (!inc[i][a]) return 0;
last = u[a]; a = dp[i][a];
}
}
return 1;
}
bool checkdec (int a, int x) { //decreasing upwards
if (a == x) return 1;
//cout << a << " | " << x << '\n';
int e = dep[a] - dep[x];
//cout << e << " dd\n";
int last = 1e9;
for (int i = MM - 1; i >= 0; i--) {
if (e & (1 << i)) {
if (u[a] > last) return 0;
if (!decc[i][a]) return 0;
last = u[a]; a = dp[i][a];
}
}
return 1;
}
int gettop (int a, int x) {
int uu = dep[a] - dep[x];
int t = u[a];
for (int i = MM - 1; i >= 0; i--) {
if (uu & (1 << i)) {
t = top[i][a];
a = dp[i][a];
}
}
return t;
}
int getmx (int a, int x) {
int uu = dep[a] - dep[x];
int t = 0;
for (int i = MM - 1; i >= 0; i--) {
if (uu & (1 << i)) {
t = max(t, mx[i][a]);
a = dp[i][a];
}
}
return t;
}
bool check (int a, int b, int x) {
if (!checkinc(b, x)) return 0;
if (!checkdec(a, x)) return 0;
if (gettop(b, x) > gettop(a, x)) return 0;
return 1;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
int l = 0;
for (int i = 1; i <= n + q - 1; i++) {
char x;
cin >> x;
if (x == 'S') {
cnt++;
int a, b;
cin >> a >> b;
adj[a].push_back({b, cnt});
adj[b].push_back({a, cnt});
} else if (x == 'Q') {
t[++l] = cnt;
int a, b;
cin >> a >> b;
queries[l] = {a, b};
}
}
calc(1, 0);
for (int i = 1; i < MM; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][dp[i - 1][j]];
top[i][j] = top[i - 1][dp[i - 1][j]];
mx[i][j] = max(mx[i - 1][j], mx[i - 1][dp[i - 1][j]]);
inc[i][j] = inc[i - 1][j] & inc[i - 1][dp[i - 1][j]];
decc[i][j] = decc[i - 1][j] & decc[i - 1][dp[i - 1][j]];
inc[i][j] &= (top[i - 1][j] < u[dp[i - 1][j]]);
decc[i][j] &= (top[i - 1][j] > u[dp[i - 1][j]]);
}
}
for (int i = 1; i <= l; i++) {
vector <int> pp;
int x = lca(queries[i].first, queries[i].second);
int a = queries[i].first, b = queries[i].second;
//cout << a << " | " << x << " " << b << '\n';
bool flag = 0;
if (a == b) {
flag = 1;
} else if (a == x) {
//cout << checkinc(b, x) << " " << getmx(b, x) << '\n';
flag = checkinc(b, x) & getmx(b, x) <= t[i];
} else if (b == x) {
//cout << checkdec(a, x) << " " << getmx(a, x) << '\n';
flag = checkdec(a, x) & getmx(a, x) <= t[i];
} else {
//cout << check(a, b, x) << " " << getmx(a, x) << " " << getmx(b, x) << '\n';
flag = check(a, b, x) & getmx(a, x) <= t[i] && getmx(b, x) <= t[i];
}
cout << (flag ? "yes\n" : "no\n");
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:148:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
148 | flag = checkinc(b, x) & getmx(b, x) <= t[i];
| ~~~~~~~~~~~~^~~~~~~
servers.cpp:151:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
151 | flag = checkdec(a, x) & getmx(a, x) <= t[i];
| ~~~~~~~~~~~~^~~~~~~
servers.cpp:154:49: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
154 | flag = check(a, b, x) & getmx(a, x) <= t[i] && getmx(b, x) <= t[i];
| ~~~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
48468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
48468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
48468 KB |
Output is correct |
| 2 |
Correct |
89 ms |
53444 KB |
Output is correct |
| 3 |
Correct |
85 ms |
53448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
48468 KB |
Output is correct |
| 2 |
Correct |
89 ms |
53444 KB |
Output is correct |
| 3 |
Correct |
85 ms |
53448 KB |
Output is correct |
| 4 |
Incorrect |
33 ms |
48468 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
48388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
48388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
48468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
48468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
48468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
48468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
48372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
48372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
