#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define db(val) "[" #val " = " << (val) << "] "
const ll mod = 1e9 + 7;
const int maxn = 1e5 + 4;
const int INF = 1e9;
struct Node {
int fi, se;
bool operator < (const Node &other) const {
return se > other.se;
}
};
struct seg_tree {
vector<int> t;
seg_tree() {
t.resize(4 * maxn);
}
void update(int pos, int val, int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) {
t[v] += val;
return;
}
int m = (l + r) / 2;
if (pos <= m) update(pos, val, 2 * v, l, m);
else update(pos, val, 2 * v + 1, m + 1, r);
}
int get(int pos, int v = 1, int l = 1, int r = maxn - 1) {
if (l == r) return t[v];
int m = (l + r) / 2;
if (pos <= m) return get(pos, 2 * v, l, m);
else return get(pos, 2 * v, l, m) + get(pos, 2 * v + 1, m + 1, r);
}
} IT;
int n, k, leave[maxn], join[maxn], reach[maxn], res[maxn];
set<Node> adj[maxn];
vector<int> query_c[maxn];
set<pair<int,int>> query_q[maxn];
map<int,int> L;
stack<pair<int,int>> rev;
void dfs_in(int u, int p, int pre) {
auto it = query_q[u].begin();
while (it != query_q[u].end()) {
auto idx = L.find(it->fi);
if (idx == L.end()) {
it++;
continue;
}
res[it->se] = -1;
it = query_q[u].erase(it);
}
for (auto it : query_c[u])
res[it] += IT.get(it) + 1;
for (auto it : adj[u]) {
int v = it.fi, w = it.se;
if (w < pre && v != p)
dfs_in(v, u, w);
}
}
void dfs_out(int u, int p, int pre) {
L[u] = pre;
IT.update(pre, 1);
rev.push({pre, 1});
for (auto it : adj[u]) {
int v = it.fi, w = it.se;
if (w > pre && v != p)
dfs_out(v, u, w);
}
}
void Solve(int u) {
L.clear();
L[u] = 0;
for (auto it : adj[u]) {
int v = it.fi, w = it.se;
dfs_in(v, u, w);
dfs_out(v, u, w);
}
auto it = query_q[u].begin();
while (it != query_q[u].end()) {
auto idx = L.find(it->fi);
if (idx == L.end() || idx->se > it->se) {
it++;
continue;
}
res[it->se] = -1;
it = query_q[u].erase(it);
}
// if (u == 1) clog << IT.get(4);
for (auto it : query_c[u]) {
// if (u == 1) clog << it << '\n';
res[it] += IT.get(it) + 1;
}
while (!rev.empty()) {
int u, i; tie(u, i) = rev.top(); rev.pop();
IT.update(u, -i);
}
}
struct Centroid_Decomposition {
int sz[maxn];
int dfs(int u, int p) {
sz[u] = 1;
for (auto it : adj[u])
if (it.fi != p)
sz[u] += dfs(it.fi, u);
return sz[u];
}
int Centroid(int u, int p, int tot) {
for (auto it : adj[u])
if (it.fi != p && sz[it.fi] > tot / 2)
return Centroid(it.fi, u, tot);
return u;
}
void build(int u) {
int tot = dfs(u, 0);
int c = Centroid(u, 0, tot);
Solve(c);
vector<Node> del(adj[c].begin(), adj[c].end());
for (auto it : del) {
adj[c].erase(it);
adj[it.fi].erase(adj[it.fi].find({c, it.se}));
build(it.fi);
}
}
} Cen;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen(".INP", "r", stdin);
//freopen(".OUT", "w", stdout);
cin >> n >> k;
for (int i = 1; i <= n + k - 1; i++)
res[i] = -3;
for (int i = 1; i <= n + k - 1; i++) {
char type; int u; cin >> type >> u;
if (type == 'S') {
int v; cin >> v;
adj[u].insert({v, i});
adj[v].insert({u, i});
}
else if (type == 'Q') {
int v; cin >> v;
if (u == v) res[i] = -1;
else {
query_q[v].insert({u, i});
res[i] = -2;
}
}
else {
query_c[u].pb(i);
res[i] = 0;
}
}
Cen.build(1);
for (int i = 1; i <= n + k - 1; i++)
if (res[i] != -3) {
if (res[i] >= 0) cout << res[i];
else cout << (res[i] == -1 ? "yes" : "no");
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
20896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
61 ms |
20896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
21064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
21064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
20884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
20884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
20876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
20876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
20964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
20964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
20972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
20972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
