#include <bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2","popcnt","sse4","abm")
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 4> p4i;
const int MXN = 120005, LG = 17;
int n, q;
vector<pii> edge[MXN];
vector<pii> qc[MXN];
vector<p4i> qq;
int ans[MXN * 2];
int d[MXN];
int p[LG][MXN], big[LG][MXN], lst[LG][MXN];
bitset<MXN> isP[LG], isN[LG];
void DFS(int id, int par, int dep) {
p[0][id] = par;
d[id] = dep;
for (auto &[e, i] : edge[id]) {
if (i == par) continue;
big[0][i] = e;
lst[0][i] = e;
DFS(i, id, dep + 1);
}
}
void MAKE_TREE() {
DFS(1, 1, 0);
isP[0].set();
isN[0].set();
FOR(w, 1, LG) {
FOR(i, 1, n + 1) {
int pp = p[w - 1][i];
p[w][i] = p[w - 1][pp];
big[w][i] = max(big[w - 1][i], big[w - 1][pp]);
lst[w][i] = lst[w - 1][pp];
isP[w][i] = (isP[w - 1][i]) & (isP[w - 1][pp]) & (lst[w - 1][i] < lst[0][pp]);
isN[w][i] = (isN[w - 1][i]) & (isN[w - 1][pp]) & (lst[w - 1][i] > lst[0][pp]);
}
}
}
namespace NSBL {
int JUMP(int x, int k) {
FOR(w, 0, LG) if (k & (1 << w)) x = p[w][x];
return x;
}
int LCA(int x, int y) {
if (d[x] < d[y]) swap(x, y);
x = JUMP(x, d[x] - d[y]);
if (x == y) return x;
for (int w = LG - 1; w >= 0; w--) {
if (p[w][x] == p[w][y]) continue;
x = p[w][x];
y = p[w][y];
}
return p[0][x];
}
int GET_BIG(int x, int k) {
int ans = 0;
FOR(w, 0, LG) if (k & (1 << w)) {
ans = max(ans, big[w][x]);
x = p[w][x];
}
return ans;
}
bool PS(int x, int k) {
int L = lst[0][x];
x = p[0][x];
k--;
FOR(w, 0, LG) if (k & (1 << w)) {
if (L > lst[0][x] || !isP[w][x]) return false;
L = lst[w][x];
x = p[w][x];
}
return true;
}
bool NG(int x, int k) {
int L = lst[0][x];
x = p[0][x];
k--;
FOR(w, 0, LG) if (k & (1 << w)) {
if (L < lst[0][x] || !isN[w][x]) return false;
L = lst[w][x];
x = p[w][x];
}
return true;
}
bool calc(int u, int v, int t) {
debug(u, v, t);
if (u == v) return true;
int lca = LCA(u, v);
int b = max(GET_BIG(u, d[u] - d[lca]), GET_BIG(v, d[v] - d[lca]));
if (b > t) return false;
if (lca == u) {
return NG(v, d[v] - d[u]);
} else if (lca == v) {
return PS(u, d[u] - d[v]);
} else {
int su = JUMP(u, d[u] - d[lca] - 1), sv = JUMP(v, d[v] - d[lca] - 1);
return NG(v, d[v] - d[lca]) && PS(u, d[u] - d[lca]) && (lst[0][su] < lst[0][sv]);
}
return false;
}
void DO() {
for (auto [u, v, t, aid] : qq) {
ans[aid] = (calc(v, u, t) ? -2 : -3);
}
}
}
namespace NSCD {
void DO() {
}
}
void miku() {
cin >> n >> q;
int ec = 0;
FOR(i, 0, q + n - 1) {
char c;
int a, b;
cin >> c;
if (c == 'S') {
cin >> a >> b;
ec++;
edge[a].push_back(mp(i, b));
edge[b].push_back(mp(i, a));
ans[i] = -1;
} else if (c == 'Q') {
cin >> a >> b;
qq.push_back({a, b, ec, i});
} else {
cin >> a;
qc[a].push_back(mp(ec, i));
}
}
MAKE_TREE();
NSBL::DO();
NSCD::DO();
FOR(i, 0, q + n - 1) {
if (ans[i] == -1) continue;
else if (ans[i] < 0) cout << (ans[i] == -2 ? "yes" : "no") << '\n';
else cout << ans[i] << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
servers.cpp: In function 'bool NSBL::calc(int, int, int)':
servers.cpp:13:20: warning: statement has no effect [-Wunused-value]
13 | #define debug(...) 39
| ^~
servers.cpp:114:9: note: in expansion of macro 'debug'
114 | debug(u, v, t);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
10184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
10184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
10204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
10204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
10256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
10256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
10196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
10196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
10164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
10164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
10184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
10184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
