#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define INF 1e9
vector<vector<pii>> G;
vector<bool> removed;
vector<int> S;
int dfs(int v, int p){
S[v] = 1;
for(auto [u, w] : G[v]){
if(u == p || removed[u]) continue;
S[v] += dfs(u, v);
}
return S[v];
}
stack<int> weights;
int centroid(int v, int n, int p){
for(auto [u, w] : G[v]){
if(u == p || removed[u]) continue;
if(2 * S[u] > n){
weights.push(w);
return centroid(u, n, v);
}
}
return v;
}
struct edge{
char d;
int m, M;
edge(char c = '0') : d(c) {}
edge(int w) : d('1'), m(w), M(w) {}
edge(int m, int M, char d) : m(m), M(M), d(d) {}
edge operator+(edge const& other){
if(d == '0')
return other;
if(other.d == '0')
return d;
if(d == '?' || other.d == '?')
return edge('?');
if(d == 'U' && other.d == 'D')
return edge('?');
if(d == 'D' && other.d == 'U')
return edge('?');
if(d == '1' && other.d == '1'){
if (m < other.m)
return edge(m, other.m, 'U');
else
return edge(other.m, m, 'D');
}
if(d == '1'){
if(other.d == 'U' && M < other.m)
return edge(m, other.M, 'U');
if(other.d == 'D' && m > other.M)
return edge(other.m, M, 'D');
}
if(d == 'U')
if(M < other.m)
return edge(m, other.M, 'U');
if(d == 'D')
if(m > other.M)
return edge(other.m, M, 'U');
return edge('?');
}
};
vector<map<int, edge>> mp;
vector<set<int>> asdfgsa;
vector<int> parent, depth;
void dfs2(int v, int p, edge e, int centr){
mp[centr][v] = e;
for(auto [u, w] : G[v]){
if(u == p || removed[u]) continue;
dfs2(u, v, e + edge(w), centr);
}
}
int centroid_decomp(int v, int p, int d = 0){
int centr = centroid(v, dfs(v, p), p);
depth[centr] = d;
removed[centr] = 1;
dfs2(centr, 0, edge(), centr);
for(auto [u, w] : G[centr]){
if(u == p || removed[u]) continue;
parent[centroid_decomp(u, centr, d + 1)] = centr;
}
return centr;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, k;
cin >> n >> k;
G.resize(n + 1);
S.resize(n + 1);
mp.resize(n + 1);
removed.resize(n + 1);
depth.resize(n + 1);
parent.resize(n + 1);
vector<pair<int, pii>> Q;
Q.reserve(k);
for(int i = 0; i < n + k - 1; i++){
char c;
cin >> c;
if(c == 'S'){
int a, b;
cin >> a >> b;
G[a].push_back({b, i});
G[b].push_back({a, i});
}
if(c == 'Q'){
int a, d;
cin >> a >> d;
Q.push_back({i, {a, d}});
}
if(c == 'C'){
int d;
cin >> d;
Q.push_back({i, {-1, d}});
}
}
centroid_decomp(1, 0);
for(auto [t, q] : Q){
int a = q.first, d = q.second;
if(a == -1){
cout << "1\n";
}
else{
if(a == d){
cout << "yes\n";
continue;
}
int _a = a, _d = d;
if(depth[_a] < depth[_d])
swap(_a, _d);
while(depth[_a] != depth[_d])
_a = parent[_a];
while(_a != _d){
_a = parent[_a];
_d = parent[_d];
}
edge e1 = mp[_a][d];
if(e1.d == 'U')
e1.d = 'D';
else if(e1.d == 'D')
e1.d = 'U';
edge e = e1 + mp[_a][a];
if((e.d == 'U' || e.d == '1') && e.M < t)
cout << "yes\n";
else
cout << "no\n";
}
}
}
Compilation message
servers.cpp: In constructor 'edge::edge(int, int, char)':
servers.cpp:36:12: warning: 'edge::M' will be initialized after [-Wreorder]
36 | int m, M;
| ^
servers.cpp:35:10: warning: 'char edge::d' [-Wreorder]
35 | char d;
| ^
servers.cpp:40:5: warning: when initialized here [-Wreorder]
40 | edge(int m, int M, char d) : m(m), M(M), d(d) {}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
