#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int inf = 1000000100;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
struct Query {
bool type;
int time;
int v;
};
struct Edge {
int to;
int time;
};
int main() {
int N, K;
cin >> N >> K;
vector<tuple<int, int, int>> Q(N + K - 1);
vector<vector<Edge>> Tree(N);
vector<int> ans(N + K - 1, -1);
REP(i, N + K - 1) {
auto &[c, a, b] = Q[i];
char s;
cin >> s >> a;
--a;
if (s == 'S') c = 0;
if (s == 'Q') c = 1;
if (s == 'C') c = 2;
if (c != 2) {
cin >> b;
--b;
}
if (c == 0) {
Tree[a].push_back({b, i});
Tree[b].push_back({a, i});
}
if (c == 1 and a == b) ans[i] = 1;
}
vector<vector<Query>> qv(N);
REP(i, N + K - 1) {
const auto &[c, a, b] = Q[i];
if (c == 0) continue;
if (c == 1) qv[a].push_back({false, i, b});
if (c == 2) qv[a].push_back({true, i, 0});
}
vector<bool> is_valid(N, true);
vector<int> subsize(N);
auto centroid_decompose = [&](auto &&self, const int root, auto &solve) -> void {
{
auto dfs = [&](auto &&self, const int v, const int p) -> int {
subsize[v] = 1;
for (const auto &[to, dust] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
subsize[v] += self(self, to, v);
}
return subsize[v];
};
dfs(dfs, root, -1);
}
const int count_v = subsize[root];
int centroid = -1;
{
auto dfs = [&](auto &&self, const int v, const int p) -> void {
bool is_centroid = true;
for (const auto &[to, dust] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
self(self, to, v);
if (subsize[to] > count_v / 2) is_centroid = false;
}
if (count_v - subsize[v] > count_v / 2) is_centroid = false;
if (is_centroid) centroid = v;
};
dfs(dfs, root, -1);
}
solve(centroid);
{
is_valid[centroid] = false;
vector<vector<int>> vertices;
for (const auto &[to, dust] : Tree[centroid]) {
if (not is_valid[to]) continue;
vertices.push_back({});
auto dfs = [&](auto &&self, const int v, const int p) -> void {
vertices.back().push_back(v);
is_valid[v] = false;
for (const auto &[to, dust2] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
self(self, to, v);
}
};
dfs(dfs, to, centroid);
}
int cnt = 0;
for (const auto &ver : vertices) {
for (const int ve : ver) is_valid[ve] = true;
self(self, ver[0], solve);
for (const int ve : ver) is_valid[ve] = false;
++cnt;
}
}
};
vector<bool> is_inc(N), is_dec(N);
vector<int> froot(N), pa_time(N);
auto answer_query = [&](const int centroid) {
{
auto dfs = [&](auto &&self, const int v, const int p, const int last_time,
const int fr) -> void {
froot[v] = fr;
pa_time[v] = last_time;
for (const auto &[to, time] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
if (is_inc[v] and (last_time == -1 or time > last_time)) is_inc[to] = true;
if (is_dec[v] and (last_time == -1 or time < last_time)) is_dec[to] = true;
self(self, to, v, time, fr == -1 ? to : fr);
}
};
is_inc[centroid] = is_dec[centroid] = true;
dfs(dfs, centroid, -1, -1, -1);
}
{
auto dfs = [&](auto &&self, const int v, const int p) -> void {
for (const auto &[type, id, b] : qv[v]) {
if (not type) {
if (not is_valid[b]) continue;
if (froot[v] == froot[b]) continue;
if (ans[id] != -1) continue;
bool res = is_inc[v] and is_dec[b];
res &= (v == centroid ? pa_time[froot[b]] : pa_time[v]) <= id;
res &= (v == centroid ? inf : pa_time[froot[v]]) >=
(b == centroid ? -1 : pa_time[froot[b]]);
ans[id] = res;
}
}
for (const auto &[to, dust] : Tree[v]) {
if (not is_valid[to]) continue;
if (to == p) continue;
self(self, to, v);
}
};
dfs(dfs, centroid, -1);
}
};
centroid_decompose(centroid_decompose, 0, answer_query);
REP(i, N + K - 1) {
if (ans[i] == -1) continue;
if (get<0>(Q[i]) == 1) {
cout << (ans[i] ? "yes" : "no") << '\n';
} else {
cout << ans[i] << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
4640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
4640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4800 KB |
Output is correct |
| 2 |
Correct |
244 ms |
27772 KB |
Output is correct |
| 3 |
Correct |
253 ms |
27816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4800 KB |
Output is correct |
| 2 |
Correct |
244 ms |
27772 KB |
Output is correct |
| 3 |
Correct |
253 ms |
27816 KB |
Output is correct |
| 4 |
Incorrect |
62 ms |
5496 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
4672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
4672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
4732 KB |
Output is correct |
| 2 |
Correct |
365 ms |
22576 KB |
Output is correct |
| 3 |
Correct |
519 ms |
22560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
4732 KB |
Output is correct |
| 2 |
Correct |
365 ms |
22576 KB |
Output is correct |
| 3 |
Correct |
519 ms |
22560 KB |
Output is correct |
| 4 |
Incorrect |
54 ms |
5492 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
4748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
4748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
4740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
4740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
