#include <bits/stdc++.h>
using namespace std;
#define cerr cerr << "DEBUG "
constexpr int N = 24e4 + 10;
int n, k;
vector<pair<int, int>> qp[N];
vector<int> qu[N];
vector<pair<int, int>> up, down;
pair<int, int> tmp[N];
vector<pair<int, pair<int, int>>> pairs;
vector<int> verts;
bool mark[N];
int sz[N];
vector<pair<int, int>> g[N];
bool used[N];
long long ans[N];
int parent[N];
int centroid(int v, int p, int m) {
tmp[v] = make_pair(INT_MAX, INT_MAX);
verts.push_back(v);
mark[v] = true;
int ret = 0, cool = 1;
sz[v] = 1;
for (auto &e : g[v]) {
int u = e.first;
if (u != p && !used[u]) {
ret ^= ~centroid(u, v, m);
cool &= sz[u] <= m / 2;
sz[v] += sz[u];
}
}
//cerr << cool << '\n';
return cool && m - sz[v] <= m / 2 ? v : ~ret;
}
void dfs(int v, int p, int fe, int f, int s) {
//cerr << "DFSING: " << v << '\n';
sz[v] = 1;
parent[v] = fe;
if (~f) {
for (auto &query : qu[v]) {
up.push_back({fe, query});
}
for (auto &query : qp[v]) {
pairs.push_back({query.first, {fe, query.second}});
}
}
if (~s) {
down.push_back({fe, s});
tmp[v] = make_pair(fe, s);
}
for (auto &e : g[v]) {
int u = e.first, w = e.second;
if (u != p && !used[u]) {
dfs(u, v, fe, w < f ? w : -1, w > s ? w : -1);
sz[v] += sz[u];
}
}
//cerr << "UNDFSING: " << v << ' ' << sz[v] << '\n';
}
int fen[N];
void update(int i, int x) {
for (++i; i < N; i += i & -i) {
fen[i] += x;
}
}
int query(int i) {
int ret = 0;
for (++i; i > 0; i -= i & -i) {
ret += fen[i];
}
return ret;
}
void solve() {
static vector<int> vec[N];
auto &a = up, &b = down;
for (int i = 0; i < (int) b.size(); ++i) {
vec[i].clear();
}
for (auto &x : a) {
auto p = upper_bound(b.begin(), b.end(), make_pair(x.first, INT_MAX));
ans[x.second]++; // for centroid
if (p != b.end()) {
vec[p - b.begin()].push_back(x.second);
}
}
for (int i = (int) b.size() - 1; i >= 0; --i) {
update(b[i].second, +1);
for (auto &x : vec[i]) {
ans[x] += query(x);
}
}
for (auto &x : b) {
update(x.first, -1);
}
}
void decompose(int v, int m) {
verts.clear();
int cent = centroid(v, -1, m);
//cerr << v << ' ' << cent << ' ' << m << '\n';
up.clear();
down.clear();
pairs.clear();
/*for (int i = 0; i < n; ++i) {
cout << sz[i] << ' ';
}
cout << '\n';*/
for (auto &e : g[cent]) {
int u = e.first, w = e.second;
if (!used[u]) {
//cerr << u << '\n';
dfs(u, cent, w, w, w);
}
}
/*for (int i = 0; i < n; ++i) {
cout << sz[i] << ' ';
}
cout << '\n';*/
// calc for pairs in subtrees
sort(down.begin(), down.end());
solve();
for (auto &pr : pairs) {
int x = pr.first;
if (parent[x] == pr.second.first) {
continue;
}
if (x == cent) {
ans[pr.second.second] = 1;
} else if (mark[x]) {
bool ok = pr.second.first < tmp[x].first && tmp[x].second < pr.second.second;
ans[pr.second.second] = ok;
}
}
// calc for pairs from centroid
for (auto &query : qp[cent]) {
if (mark[query.first]) {
ans[query.second] = query.first == cent || tmp[query.first].second < query.second;
}
}
for (auto &query : qu[cent]) {
ans[query] += 1 + down.size();
}
for (auto &v : verts) {
mark[v] = false;
}
used[cent] = true;
for (auto &e : g[cent]) {
int u = e.first;
if (!used[u]) {
//cerr << "DOING: " << u << ' ' << sz[u] << '\n';
decompose(u, sz[u]);
}
}
}
int qtype[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n + k - 1; ++i) {
char op;
cin >> op;
int v;
cin >> v;
--v;
if (op == 'S') {
int u;
cin >> u;
--u;
g[v].push_back({u, i});
g[u].push_back({v, i});
} else if (op == 'Q') {
qtype[i] = 1;
int u;
cin >> u;
--u;
qp[u].push_back({v, i});
} else {
qtype[i] = 2;
qu[v].push_back(i);
}
}
decompose(0, n);
for (int i = 0; i < n + k - 1; ++i) {
if (qtype[i] == 1) {
cout << (ans[i] ? "yes" : "no") << '\n';
} else if (qtype[i] == 2) {
cout << ans[i] << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
28048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
28048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
27976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
27976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
26688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
26688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
26704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
26704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
26676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
26676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
28020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
28020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
