#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
const int N = 120000;
int n, q;
struct AIB
{
int aib[2 * N + 5];
vector<int> descos;
inline int lsb(int x) {return x & -x;}
void update(int pos, int val)
{
while(pos < n + q)
aib[pos] += val,
descos.push_back(pos),
pos += lsb(pos);
}
int query(int pos)
{
int ans = 0;
while(pos)
ans += aib[pos],
pos -= lsb(pos);
return ans;
}
void sterge()
{
for(auto i : descos)
aib[i] = 0;
descos.clear();
}
} ds;
struct Query
{
char type;
int to, time;
};
vector<Query> qry[N + 5];
vector<pii> vec[N + 5];
int ans[2 * N + 5], sz[N + 5], muchtopapa[N + 5];
int crdcr[N + 5], papa[N + 5], papasubc[N + 5];
bool viz[N + 5], amdat[N + 5];
void dfssz(int nod, int papa)
{
sz[nod] = 1;
for(auto [i, j] : vec[nod])
if(!viz[i] && i != papa)
dfssz(i, nod), sz[nod] += sz[i];
}
int dfsCentroid(int nod, int szinit)
{
for(auto [i, j] : vec[nod])
if(!viz[i] && sz[i] < sz[nod] && 2 * sz[i] >= szinit)
return dfsCentroid(i, szinit);
return nod;
}
void dfs(int nod, vector<int> &x)
{
x.push_back(nod);
amdat[nod] = true;
for(auto [i, j] : vec[nod])
{
if(viz[i] || i == papa[nod])
continue;
papa[i] = nod;
papasubc[i] = papasubc[nod];
muchtopapa[i] = j;
crdcr[i] = 0;
if(j < muchtopapa[nod] && (crdcr[nod] & 1))
crdcr[i] ++;
if(j > muchtopapa[nod] && (crdcr[nod] & 2))
crdcr[i] += 2;
dfs(i, x);
}
}
//crdcr[nod] & 1 => crescator de la nod in sus
//crdcr[nod] & 2 => descrescator de la nod in sus
void doCentroid(int nod)
{
dfssz(nod, 0);
int centr = dfsCentroid(nod, sz[nod]);
vector<pair<int, vector<int>>> subarb;
for(auto [i, j] : vec[centr])
{
if(viz[i])
continue;
subarb.push_back({i, {}});
papa[i] = centr;
papasubc[i] = i;
muchtopapa[i] = j;
crdcr[i] = 3;
dfs(i, subarb.back().sc);
}
sort(all(subarb), [&](pair<int, vector<int>> a, pair<int, vector<int>> b)
{
return muchtopapa[a.fr] < muchtopapa[b.fr];
});
amdat[centr] = true;
crdcr[centr] = 3;
ds.update(1, 1);
for(auto [i, v] : subarb)
{
for(auto j : v)
for(auto k : qry[j])
{
if(k.type == 'c')
{
//cout << centr << " " << j << " " << k.to << '\n';
if(muchtopapa[papasubc[j]] <= k.time && (crdcr[j] & 1))
ans[k.time] += ds.query(k.time);
}
else
{
//cout << centr << " " << j << " " << k.to << " " << k.time << '\n';
if(amdat[k.to] && muchtopapa[papasubc[k.to]] > muchtopapa[papasubc[j]] &&
muchtopapa[k.to] <= k.time && (crdcr[k.to] & 2) && (crdcr[j] & 1))
ans[k.time] = -1;
}
}
for(auto j : v)
if(crdcr[j] & 2)
ds.update(muchtopapa[j], 1);
}
ds.update(1, -1);
for(auto i : qry[centr])
{
if(i.type == 'c')
ans[i.time] += ds.query(i.time);
else if(amdat[i.to] && (crdcr[i.to] & 2) && muchtopapa[i.to] <= i.time)
ans[i.time] = -1;
}
ds.sterge();
amdat[centr] = false;
for(auto i : subarb)
for(auto j : i.sc)
amdat[j] = false;
viz[centr] = true;
for(auto [i, j] : vec[centr])
if(!viz[i])
doCentroid(i);
}
int main()
{
cin >> n >> q;
for(int i = 1; i < n + q; i ++)
{
char t;
cin >> t;
if(t == 'S')
{
int u, v;
cin >> u >> v;
vec[u].push_back({v, i});
vec[v].push_back({u, i});
ans[i] = -69;
}
if(t == 'Q')
{
int u, v;
cin >> u >> v;
qry[v].push_back({'q', u, i});
ans[i] = -2;
}
if(t == 'C')
{
int u;
cin >> u;
qry[u].push_back({'c', 0, i});
}
}
doCentroid(1);
for(int i = 1; i < n + q; i ++)
{
if(ans[i] == -1)
cout << "yes\n";
else if(ans[i] == -2)
cout << "no\n";
else if(ans[i] >= 0)
cout << ans[i] + 1 << '\n';
}
}
/*
6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6
*/
Compilation message
servers.cpp: In function 'void dfssz(int, int)':
servers.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [i, j] : vec[nod])
| ^
servers.cpp: In function 'int dfsCentroid(int, int)':
servers.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
62 | for(auto [i, j] : vec[nod])
| ^
servers.cpp: In function 'void dfs(int, std::vector<int>&)':
servers.cpp:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
72 | for(auto [i, j] : vec[nod])
| ^
servers.cpp: In function 'void doCentroid(int)':
servers.cpp:96:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
96 | for(auto [i, j] : vec[centr])
| ^
servers.cpp:114:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
114 | for(auto [i, v] : subarb)
| ^
servers.cpp:152:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
152 | for(auto [i, j] : vec[centr])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
13296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
13296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
13384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
13384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
13276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
13276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
13396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
13404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
13404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
