#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 2e5 + 10;
bool dd[N];
int sz[N], ans[N];
vector<pair<int, int>> adj[N], query1[N];
vector<int> query2[N];
int n, k, cnt[N], type[N];
int calc(int u, int par) {
sz[u] = 1;
for(auto &[v, w] : adj[u]) if (!dd[v] && v != par)
sz[u] += calc(v, u);
return sz[u];
}
int getcentr(int u, int par, int cnt) {
for(auto &[v, w] : adj[u]) if (!dd[v] && v != par && sz[v] > 2 * cnt)
return getcentr(v, u, cnt);
return u;
}
int bit[N << 1];
void up(int pos, int val) {
while (pos <= k) {
bit[pos] += val;
pos += pos & -pos;
}
}
int get(int pos) {
int ret = 0;
while (pos) {
ret += bit[pos];
pos -= pos & -pos;
}
return ret;
}
void dfs1(int u, int pre) {
up(pre, 1);
cnt[u] = pre;
for(auto &[v, w] : adj[u]) if (!dd[v] && w > pre) {
dfs1(v, w);
}
}
void dfs2(int u, int pre) {
for(int &idx : query2[u]) {
ans[idx] += get(idx);
}
for(auto &[a, idx] : query1[u]) {
ans[idx] |= (cnt[a] > 0 && cnt[a] < idx);
}
for(auto &[v, w] : adj[u]) if (!dd[v] && w < pre) {
dfs2(v, w);
}
}
void dfs3(int u, int pre) {
up(pre, -1);
cnt[u] = 0;
for(auto &[v, w] : adj[u]) if (!dd[v] && w > pre) {
dfs3(v, w);
}
}
void centroid(int u) {
int node = getcentr(u, u, calc(u, u));
dd[node] = 1;
// cout << node << endl;
vector<pair<int, int> > lst;
for(auto &[v, w] : adj[node]) if (!dd[v]) lst.emplace_back(-w, v);
sort(lst.begin(), lst.end());
for(auto &[w, v] : lst) {
w = -w;
up(w, 1);
dfs2(v, w);
up(w, -1);
dfs1(v, w);
}
for(int &idx : query2[node]) {
ans[idx] += get(idx);
}
for(auto &[a, idx] : query1[node]) {
ans[idx] |= (cnt[a] > 0 && cnt[a] < idx);
}
for(auto &[w, v] : lst) {
dfs3(v, w);
}
for(auto &[v, w] : adj[node]) if (!dd[v]) centroid(v);
}
int main() {
#define task ""
cin.tie(0) -> sync_with_stdio(0);
if (fopen ("task.inp", "r")) {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
}
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> n >> k;
k = n + k - 1;
for(int i = 1; i <= k; i++) {
char c; cin >> c;
if (c == 'S') {
int a, b; cin >> a >> b;
adj[a].emplace_back(b, i);
adj[b].emplace_back(a, i);
}
if (c == 'Q') {
int a, d; cin >> a >> d;
if (a == d) ans[i] = 1;
query1[d].emplace_back(a, i);
type[i] = 1;
}
if (c == 'C') {
int d; cin >> d;
query2[d].push_back(i);
type[i] = 2;
ans[i] = 1;
}
}
centroid(1);
for(int i = 1; i <= k; i++) {
if (type[i] == 1) cout << (ans[i] ? "yes\n" : "no\n");
else if (type[i] == 2) cout << ans[i] << endl;
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:104:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | freopen ("task.inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:105:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | freopen ("task.out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:108:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | freopen (task".inp", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:109:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen (task".out", "w", stdout);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
18636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
18636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
18628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
18628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
18568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
18568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
18652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
18652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
18672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
18672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
18564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
18564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
