#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;
const int N = 12e4 + 5, S = 17;
int n, nq, f[N], anc[N], sz[N], ans[N], dis[N], par[N][S], tang[N], giam[N];
bool block[N], inc[N], red[N];
vector <ii> ke[N];
vector <int> vt[N], update[N], cur, ques[N], bit[N];
struct sieungu {
int fi, se, th;
}; vector <sieungu> dull;
void dfs(int u, int pre, int p) {
for(auto [v, w] : ke[u]) if(!block[v] && v != pre) {
f[v] = w;
if(!p) {
anc[v] = v;
inc[v] = red[v] = 1;
vt[v].clear();
update[v].clear();
cur.push_back(v);
}
else {
inc[v] = (inc[u] && f[v] > f[u]);
red[v] = (red[u] && f[v] < f[u]);
anc[v] = anc[u];
}
if(inc[v]) {
vt[anc[v]].push_back(f[v]);
update[anc[v]].push_back(f[v]);
vt[0].push_back(f[v]);
update[0].push_back(f[v]);
}
if(red[v]) {
for(int i : ques[v]) {
if(f[v] < i) ans[i]++;
vt[0].push_back(i);
vt[anc[v]].push_back(i);
}
}
dfs(v, u, anc[v]);
}
}
void upd(int i, int x) {
x = lower_bound(vt[i].begin(), vt[i].end(), x) - vt[i].begin() + 1;
while (x < bit[i].size()) {
bit[i][x]++;
x += (x & -x);
}
}
int get(int i, int x) {
x = lower_bound(vt[i].begin(), vt[i].end(), x) - vt[i].begin() + 1;
int ret = 0;
while (x) {
ret += bit[i][x];
x -= (x & -x);
}
return ret;
}
void scan(int u, int pre) {
for(auto [v, w] : ke[u]) if(v != pre && !block[v]) {
if(red[v]) {
for(auto i : ques[v]) if(f[v] < i) {
int s1 = get(0, i) - get(0, f[anc[v]]);
int s2 = get(anc[v], i) - get(anc[v], f[anc[v]]);
ans[i] += s1 - s2;
}
}
scan(v, u);
}
}
void solve(int u) {
f[u] = 0, inc[u] = 1, red[u] = 1, anc[u] = 0;
vt[0].clear(), cur.clear(), update[0].clear();
cur.push_back(0);
dfs(u, 0, 0);
for(int i : ques[u]) vt[0].push_back(i);
for(int v : cur) {
sort(vt[v].begin(), vt[v].end());
bit[v].clear(), bit[v].resize(vt[v].size() + 1);
for(int i : update[v]) upd(v, i);
}
for(int i : ques[u]) ans[i] += get(0, i);
scan(u, 0);
}
int cnt(int u, int pre) {
sz[u] = 1;
for(auto [v, w] : ke[u]) if(v != pre && !block[v]) sz[u] += cnt(v, u);
return sz[u];
}
int centroid(int u, int pre, int cnt) {
for(auto [v, w] : ke[u]) if(!block[v] && v != pre && sz[v] > cnt / 2) return centroid(v, u, cnt);
return u;
}
void dfss(int u, int pre) {
for(auto [v, w] : ke[u]) if(v != pre) {
dis[v] = dis[u] + 1;
f[v] = w;
if(!pre) tang[v] = giam[v] = 1;
else {
tang[v] = (f[v] > f[u] ? tang[u] + 1 : 1);
giam[v] = (f[v] < f[u] ? giam[u] + 1 : 1);
}
par[v][0] = u;
for(int i = 1; i < S; i++) par[v][i] = par[par[v][i - 1]][i - 1];
dfss(v, u);
}
}
int lca(int u, int v) {
if(dis[u] < dis[v]) swap(u, v);
int delta = dis[u] - dis[v];
for(int i = S - 1; i >= 0; i--) if((delta >> i) & 1) u = par[u][i];
if(u == v) return u;
for(int i = S - 1; i >= 0; i--) if(par[u][i] != par[v][i])
u = par[u][i], v = par[v][i];
return par[v][0];
}
int pre_lca(int u, int o) {
int delta = dis[u] - dis[o] - 1;
for(int i = S - 1; i >= 0; i--) if((delta >> i) & 1) u = par[u][i];
return u;
}
void build(int u) {
int cen = centroid(u, 0, cnt(u, 0));
block[cen] = 1;
solve(cen);
for(auto [v, w] : ke[cen]) if(!block[v]) build(v);
}
main () {
cin.tie(0)->sync_with_stdio(0);
if(fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
// freopen("wa.out", "w", stdout);
}
cin >> n >> nq; nq += n - 1;
for(int i = 1; i <= nq; i++) {
char type; cin >> type;
if(type == 'S') {
int a, b; cin >> a >> b;
ke[a].push_back({b, i});
ke[b].push_back({a, i});
ans[i] = -1;
}
if(type == 'Q') {
int a, d; cin >> a >> d;
dull.push_back({a, d, i});
ans[i] = -2;
}
if(type == 'C') {
int d; cin >> d;
ques[d].push_back(i);
}
}
dfss(1, 0);
for(auto [a, d, i] : dull) {
int o = lca(a, d);
if(dis[d] - dis[o] == giam[d] - giam[o] &&
dis[a] - dis[o] == tang[a] - tang[o] &&
(f[pre_lca(d, o)] < f[pre_lca(a, o)] || a == o || d == o) &&
f[a] < i) ans[i] = -3;
else ans[i] = -4;
}
build(1);
for(int i = 1; i <= nq; i++) {
if(ans[i] >= 0) cout << ans[i] + 1 << "\n";
else if(ans[i] == -3) cout << "yes\n";
else if(ans[i] == -4) cout << "no\n";
}
}
Compilation message
servers.cpp: In function 'void upd(int, int)':
servers.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while (x < bit[i].size()) {
| ~~^~~~~~~~~~~~~~~
servers.cpp: At global scope:
servers.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
140 | main () {
| ^~~~
servers.cpp: In function 'int main()':
servers.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | freopen("task.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
17732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
17732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
17752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
17752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
17692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
17692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
17632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
17632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
17660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
17660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
17644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
17644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
