#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
#define int long long
tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> os;
vector<vector<pair<int,int>>> graph;
vector<array<int,3>> query;
int N, K, sz[MAXN], ans[MAXN], marked[MAXN], color[MAXN];
int ttt[MAXN];
int out_smallest[MAXN], out_greatest[MAXN], in_greatest[MAXN];
int get_sz(int node, int parent) {
sz[node] = 1;
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
sz[node] += get_sz(u.f, node);
}
return sz[node];
}
int find_centro(int node, int parent, int n) {
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f] && sz[u.f] * 2 >= n)
return find_centro(u.f, node, n);
}
return node;
}
void dfs(int node, int parent, int minimum_edge, int last_edge) {
out_smallest[node] = minimum_edge;
out_greatest[node] = last_edge;
for (auto u : graph[node]) {
if (u.f == parent || marked[u.f])
continue;
if (u.s > last_edge)
dfs(u.f, node, minimum_edge, u.s);
}
}
void dfs2(int node, int parent, int minimum_edge, int maximum_edge) {
in_greatest[node] = maximum_edge;
for (auto u : graph[node]) {
if (u.f == parent || marked[u.f])
continue;
if (u.s < minimum_edge)
dfs2(u.f, node, u.s, maximum_edge);
}
}
void dfs3(int node, int parent) {
if (ttt[node] > 0 && in_greatest[node] <= ttt[node])
ans[ttt[node]] += os.order_of_key({ttt[node], 0}) + 1;
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
dfs3(u.f, node);
}
}
void init(int node, int parent, int cc) {
out_greatest[node] = out_smallest[node] = -1;
in_greatest[node] = -1;
color[node] = cc;
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
init(u.f, node, cc);
}
}
void activate(int node, int parent) {
if (out_smallest[node] != -1)
os.insert({out_smallest[node], node});
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
activate(u.f, node);
}
}
void deactivate(int node, int parent) {
if (out_smallest[node] != -1)
os.erase({out_smallest[node], node});
for (auto u : graph[node]) {
if (u.f != parent && !marked[u.f])
deactivate(u.f, node);
}
}
void decompose(int node) {
get_sz(node, node);
int centro = find_centro(node, node, N);
marked[centro] = true;
int cc = 0;
os.clear();
for (auto u : graph[centro]) {
if (!marked[u.f]) {
init(u.f, node, ++cc);
dfs(u.f, node, u.s, u.s);
dfs2(u.f, node, u.s, u.s);
activate(u.f, node);
}
}
for (auto Q : query) {
if (Q[1] != -1 && color[Q[1]] != color[Q[0]]) {
// Q[1] -> Q[0] = azalan şekilde gitmeli
if (Q[0] == centro)
ans[Q[2]] += (in_greatest[Q[1]] != -1 && in_greatest[Q[1]] < Q[2]);
else if (Q[1] == centro)
ans[Q[2]] += (in_greatest[Q[0]] != -1 && in_greatest[Q[0]] < Q[2]);
else
ans[Q[2]] += (out_smallest[Q[0]] != -1 && in_greatest[Q[1]] != -1
&& in_greatest[Q[1]] < out_smallest[Q[0]] && out_greatest[Q[0]] < Q[2]);
}
}
for (auto u : graph[centro]) {
if (!marked[u.f]) {
deactivate(u.f, node);
dfs3(u.f, node);
activate(u.f, node);
}
}
for (auto u : graph[centro]) {
if (!marked[u.f])
decompose(u.f);
}
}
signed main() {
fast;
cin >> N >> K;
graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
for (int i = 1; i <= N + K - 1; i++) {
char ch;
cin >> ch;
if (ch == 'S') {
int a, b;
cin >> a >> b;
graph[a].push_back({b, i});
graph[b].push_back({a, i});
} else if (ch == 'Q') {
int a, b;
cin >> a >> b;
query.push_back({a, b, i});
} else {
int a;
cin >> a;
ttt[a] = i;
query.push_back({a, -1, i});
}
}
decompose(1);
for (auto u : query) {
if (u[1] != -1)
cout << (ans[u[2]] ? "yes\n" : "no\n");
else
cout << ans[u[2]] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
5572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
5556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
5556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
5732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
5732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
