#include <bits/stdc++.h>
template <class T> using Vec = std::vector<T>;
template <class F> struct RecLambda: private F {
explicit RecLambda(F&& f): F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator() (Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct UnionFind {
Vec<int> par;
UnionFind(const int n): par(n, -1) {}
int find(const int u) {
return par[u] < 0 ? u : par[u] = find(par[u]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
par[x] = y;
}
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, K;
std::cin >> N >> K;
Vec<int> ans(K);
Vec<Vec<std::pair<int, int>>> graph(N);
Vec<Vec<std::pair<int, int>>> detect(N);
Vec<Vec<std::pair<int, int>>> count(N);
{
UnionFind dsu(N);
int e = 0, q = 0;
for (int i = 0; i < N + K - 1; ++i) {
char c;
std::cin >> c;
if (c == 'S') {
int a, b;
std::cin >> a >> b;
a -= 1;
b -= 1;
graph[a].emplace_back(e, b);
graph[b].emplace_back(e, a);
dsu.merge(a, b);
e += 1;
} else if (c == 'Q') {
int u, v;
std::cin >> u >> v;
u -= 1;
v -= 1;
if (dsu.find(u) == dsu.find(v)) {
detect[v].emplace_back(q, u);
}
q += 1;
} else {
int u;
std::cin >> u;
u -= 1;
count[u].emplace_back(q, e);
q += 1;
}
}
}
Vec<char> done(N), to_root(N), from_root(N);
Vec<int> subtree(N), belong(N, -1);
const auto setup = RecLambda([&](auto&& dfs, const int u, const int p) -> void {
subtree[u] = 1;
for (const auto [e, v]: graph[u]) {
if (!done[v] and v != p) {
dfs(v, u);
subtree[u] += subtree[v];
}
}
});
const auto reroot = RecLambda([&](auto&& dfs, const int u, const int pe, const int b, Vec<int>& vlist, Vec<int>& elist) -> void {
belong[u] = b;
vlist.push_back(u);
if (from_root[u]) {
elist.push_back(pe);
}
for (const auto [e, v]: graph[u]) {
if (e != pe and !done[v]) {
if (e < pe) {
if (to_root[u]) {
to_root[v] = true;
}
dfs(v, e, b, vlist, elist);
} else {
if (from_root[u]) {
from_root[v] = true;
}
dfs(v, e, b, vlist, elist);
}
}
}
});
const auto centroid = RecLambda([&](auto&& dfs, const int u, const int p, const int whole) -> void {
for (const auto [e, v]: graph[u]) {
if (!done[v] and v != p and subtree[v] * 2 > whole) {
dfs(v, u, whole);
return;
}
}
done[u] = to_root[u] = from_root[u] = true;
belong[u] = 0;
Vec<Vec<int>> vlist, elist;
vlist.push_back(Vec<int>{u});
elist.push_back(Vec<int>{-1});
for (int i = 0; i < (int) graph[u].size(); ++i) {
const auto v = graph[u][i].second;
if (!done[v]) {
to_root[v] = from_root[v] = true;
const auto b = (int) vlist.size();
vlist.emplace_back();
elist.emplace_back();
reroot(v, graph[u][i].first, b, vlist.back(), elist.back());
}
}
Vec<int> all;
for (int i = 0; i < (int) elist.size(); ++i) {
std::sort(elist[i].begin(), elist[i].end());
for (const auto e: elist[i]) {
all.push_back(e);
}
}
std::sort(all.begin(), all.end());
for (int i = 1; i < (int) vlist.size(); ++i) {
for (const auto v: vlist[i]) {
for (const auto [k, w]: detect[v]) {
if (to_root[v] and ((belong[v] < belong[w] and from_root[w]) or (w == u))) {
ans[k] = -1;
}
}
for (const auto [k, e]: count[v]) {
if (to_root[v]) {
ans[k] += std::lower_bound(all.begin(), all.end(), e) - all.begin();
ans[k] -= std::lower_bound(elist[i].begin(), elist[i].end(), e) - elist[i].begin();
}
}
}
}
for (const auto [i, v]: detect[u]) {
if (from_root[v]) {
ans[i] = -1;
}
}
for (const auto [i, e]: count[u]) {
ans[i] += std::lower_bound(all.begin(), all.end(), e) - all.begin();
}
// std::cerr << "centroid: " << u << std::endl;
// for (const auto& l: vlist) {
// for (const auto v: l) {
// std::cerr << v << ' ';
// to_root[v] = from_root[v] = false;
// belong[v] = -1;
// }
// std::cerr << std::endl;
// }
for (int i = 0; i < (int) graph[u].size(); ++i) {
const auto v = graph[u][i].second;
if (!done[v]) {
setup(v, u);
dfs(v, u, subtree[v]);
}
}
});
setup(0, -1);
centroid(0, -1, N);
for (const auto x: ans) {
if (x == 0) {
std::cout << "no\n";
} else if (x == -1) {
std::cout << "yes\n";
} else {
std::cout << x << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
1576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
1576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
