#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
const int N = 120001;
int n, pr[N], sz[N], q, dep[N], p[N][17], mn[N], vt[N];
int mx[N], sze[N], bit[N+N], ans[N+N];
bool r[N];
int ar[N];
int cnt = 0;
vector<array<int, 3>> qr;
vector<pair<int, int>> adj[N];
vector<int> c[N];
void upd(int i, int val) {
i++;
while (i <= q) {
bit[i] += val;
i += (i & -i);
}
}
int get(int i) {
i++;
int ret = 0;
while (i) {
ret += bit[i];
i -= (i & -i);
}
return ret;
}
void dfs_sz(int u, int par) {
sze[u] = 1;
for (auto &[v, t] : adj[u]) {
if (r[v] || v == par)continue;
dfs_sz(v, u);
sze[u] += sz[v];
}
}
int centroid(int u, int par) {
for (auto &[v, t] : adj[u]) {
if (r[v] || v == par)continue;
if (2*sze[v] > n)return centroid(v, u);
}
return u;
}
int findp(int u) {
return pr[u] = (pr[u] == u ? u : findp(pr[u]));
}
void merge(int u, int v) {
u = findp(u), v = findp(v);
if (u == v)return;
if (sz[u] < sz[v])swap(u, v);
sz[u] += sz[v];
pr[v] = u;
}
void init(int u, int par) {
for (auto &[v, t] : adj[u]) {
if (v == par)continue;
p[v][0] = u;
dep[v] = dep[u]+1;
vt[v] = t;
mn[v] = (vt[v] < vt[u] ? mn[u] : u);
mx[v] = (vt[v] > vt[u] ? mx[u] : u);
for (int i = 1; i < 17; i++) {
p[v][i] = p[p[v][i-1]][i-1];
}
init(v, u);
}
}
int lift(int u, int k) {
for (int i = 0; i < 17; i++) {
if ((k & (1 << i)))u = p[u][i];
}
return u;
}
int lca(int u, int v) {
if (dep[u] < dep[v])swap(u, v);
u = lift(u, dep[u]-dep[v]);
if (u == v)return u;
for (int i = 16; i >= 0; i--) {
if (p[u][i] != p[v][i]) {
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}
bool sol(int u, int v) {
if (findp(u) != findp(v))return false;
int l = lca(u, v);
if (dep[mx[u]] > dep[l])return false;
if (dep[mn[v]] > dep[l])return false;
if (l == v || l == u)return true;
u = lift(u, dep[u]-dep[l]-1);
v = lift(v, dep[v]-dep[l]-1);
return (vt[v] < vt[u]);
}
int vv;
void dfs(int u, int par, int ls) {
for (auto &t : c[u]) {
ans[t] += get(t) + (vv <= t);
}
for (auto &[v, t] : adj[u]) {
if (r[v] || v == par)continue;
if (t > ls)continue;
dfs(v, u, t);
}
}
void dfs2(int u, int par, int ls) {
upd(ls, 1);
ar[cnt++] = ls;
for (auto &[v, t] : adj[u]) {
if (r[v] || v == par)continue;
if (t < ls)continue;
dfs2(v, u, t);
}
}
void cen(int u) {
dfs_sz(u, u);
n = sze[u];
u = centroid(u, u);
cnt = 0;
for (auto &[v, t] : adj[u]) {
if (r[v])continue;
vv = t;
dfs(v, u, t);
dfs2(v, u, t);
}
for (auto &t : c[u]) {
ans[t] += get(t);
}
for (int i = 0; i < cnt; i++)upd(ar[i], -1);
r[u] = true;
for (auto &[v, t] : adj[u]) {
if (r[v])continue;
cen(v);
}
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 0; i < n; i++) {
pr[i] = i, sz[i] = 1;
}
q += n-1;
bool ff = true;
for (int i = 0; i < q; i++) {
char ch;
cin >> ch;
if (ch == 'S') {
int u, v;
cin >> u >> v;
--u, --v;
qr.pb({0, u, v});
adj[u].pb({v, i});
adj[v].pb({u, i});
} else if (ch == 'Q') {
int u, v;
cin >> u >> v;
--u, --v;
qr.pb({1, u, v});
} else {
ff = false;
int u;
cin >> u;
--u;
c[u].pb(i);
qr.pb({2, u, i});
}
}
vt[0] = q+5;
init(0, 0);
if (!ff) {
for (int i = 0; i < n; i++)reverse(all(adj[i]));
cen(0);
}
for (auto &[op, u, v] : qr) {
if (!op) {
merge(u, v);
}
else if (op == 1) {
cout << (sol(u, v) ? "yes\n" : "no\n");
} else {
cout << ans[v] + 1 << "\n";
}
}
}
Compilation message
servers.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization ("unroll-loops")
|
servers.cpp: In function 'int main()':
servers.cpp:167:7: error: 'class std::vector<std::array<int, 3> >' has no member named 'pb'
167 | qr.pb({0, u, v});
| ^~
servers.cpp:168:11: error: 'class std::vector<std::pair<int, int> >' has no member named 'pb'
168 | adj[u].pb({v, i});
| ^~
servers.cpp:169:11: error: 'class std::vector<std::pair<int, int> >' has no member named 'pb'
169 | adj[v].pb({u, i});
| ^~
servers.cpp:174:7: error: 'class std::vector<std::array<int, 3> >' has no member named 'pb'
174 | qr.pb({1, u, v});
| ^~
servers.cpp:180:9: error: 'class std::vector<int>' has no member named 'pb'
180 | c[u].pb(i);
| ^~
servers.cpp:181:7: error: 'class std::vector<std::array<int, 3> >' has no member named 'pb'
181 | qr.pb({2, u, i});
| ^~
servers.cpp:187:38: error: 'all' was not declared in this scope; did you mean 'std::filesystem::perms::all'?
187 | for (int i = 0; i < n; i++)reverse(all(adj[i]));
| ^~~
| std::filesystem::perms::all
In file included from /usr/include/c++/10/filesystem:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from servers.cpp:1:
/usr/include/c++/10/bits/fs_fwd.h:148:7: note: 'std::filesystem::perms::all' declared here
148 | all = 0777,
| ^~~
