#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
const int NS = 120004;
int tr[NS];
void push(int pos, int val){
for(int i = pos; i < NS; i += (i & -i)) tr[i] += val;
}
int get(int pos){
int rv = 0;
for(int i = pos; i > 0; i -= (i & -i)) rv += tr[i];
return rv;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
vector<vector<pair<int, int>>> way(n);
vector<int> ans(n + q - 1, -1);
vector<vector<pair<int, int>>> que(n);
for(int i = 0; i < n + q - 1; ++i){
char c;
cin >> c;
if(c == 'S'){
int x, y;
cin >> x >> y;
--x, --y;
way[x].push_back({y, i});
way[y].push_back({x, i});
ans[i] = -3;
}
else if(c == 'Q'){
int x, y;
cin >> x >> y;
--x, --y;
que[y].push_back({x, i});
}
else{
int x;
cin >> x;
--x;
que[x].push_back({-1, i});
ans[i] = 0;
}
}
vector<int> chk(n), sz(n), col(n), num(n), noon(n, -1);
auto dfssz = [&](auto&&self, int x, int pr)->void{
sz[x] = 1;
for(auto&nxt:way[x]){
if(chk[nxt.first] || nxt.first == pr){
continue;
}
self(self, nxt.first, x);
sz[x] += sz[nxt.first];
}
};
auto getcent = [&](auto&&self, int x, int pr, int asz)->int{
for(auto&nxt:way[x]){
if(chk[nxt.first] || nxt.first == pr){
continue;
}
if(sz[nxt.first] * 2 > asz){
return self(self, nxt.first, x, asz);
}
}
return x;
};
auto sol = [&](auto&&self, int ct)->void{
dfssz(dfssz, ct, -1);
ct = getcent(getcent, ct, -1, sz[ct]);
chk[ct] = 1;
vector<vector<int>> t;
vector<int> sv;
vector<pair<int, int>> srt;
auto mt = [&](auto&&self, int x, int pr, int lst)->void{
noon[x] = ct;
col[x] = (int)t.size() - 1;
num[x] = lst;
if(lst >= 0 && lst < (int)1e9){
t.back().push_back(lst);
}
for(auto&nxt:way[x]){
if(nxt.first == pr || chk[nxt.first]){
continue;
}
self(self, nxt.first, x, (lst < nxt.second ? nxt.second : (int)1e9));
}
};
noon[ct] = ct;
for(auto&nxt:way[ct]){
if(chk[nxt.first]){
continue;
}
t.push_back({});
sv.push_back(nxt.second);
srt.push_back({nxt.second, nxt.first});
mt(mt, nxt.first, -1, -1);
sort(t.back().begin(), t.back().end());
}
auto upd = [&](auto&&self, int x, int pr, int lst)->void{
for(auto&i:que[x]){
if(ans[i.second] != -1) continue;
if(i.first == -1){
ans[i.second] += get(i.second);
if(sv[col[x]] <= i.second) ++ans[i.second];
}
else{
if(i.first == ct){
if(sv[col[x]] <= i.second) ans[i.second] = -5;
}
else if(noon[i.first] == ct && col[x] != col[i.first]){
if(num[i.first] <= i.second && sv[col[i.first]] >= sv[col[x]]) ans[i.second] = -5;
}
}
}
for(auto&nxt:way[x]){
if(chk[nxt.first] || nxt.first == pr || lst < nxt.second){
continue;
}
self(self, nxt.first, x, nxt.second);
}
};
sort(srt.begin(), srt.end());
reverse(srt.begin(), srt.end());
for(auto&nxt:srt){
upd(upd, nxt.second, -1, nxt.first);
for(auto&i:t[col[nxt.second]]){
push(i, 1);
}
}
for(auto&i:que[ct]){
if(ans[i.second] != -1) continue;
if(i.first == -1){
ans[i.second] += get(i.second);
}
else if(noon[i.first] == ct){
if(num[i.first] <= i.second) ans[i.second] = -5;
}
}
for(auto&nxt:srt){
for(auto&i:t[col[nxt.second]]){
push(i, -1);
}
}
for(auto&nxt:way[ct]){
if(chk[nxt.first]){
continue;
}
self(self, nxt.first);
}
};
sol(sol, 0);
for(auto&i:ans){
//cout << i << endl;
if(i != -3){
if(i == -5) cout << "yes\n";
else if(i == -1) cout << "no\n";
else cout << i << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
5888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
5944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
5944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
5920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
5908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
5908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
