#include <bits/stdc++.h>
using namespace std;
#define MAX_N 120005
#define LOG_N 17
struct DSU{
vector <int> e;
DSU(int n) : e(n ,-1) {}
int find(int x) { return e[x]<0? x : e[x]=find(e[x]); }
int size(int x) { return -e[find(x)]; }
bool join(int x ,int y){
x = find(x) ,y = find(y);
if(x == y) return false;
if(e[x] > e[y]) swap(x ,y);
e[x] += e[y]; e[y] = x;
return true;
}
};
struct query{
int type ,time ,fr ,to;
};
int tin[MAX_N] ,tout[MAX_N] ,tt;
int val[MAX_N] ,dis[MAX_N];
int par[LOG_N][MAX_N] ,inv[LOG_N][MAX_N];
vector <vector <pair<int ,int>>> adj;
void pre(int u){
tin[u] = ++tt;
for(int j = 1; (1<<j) <= dis[u]; j++){
par[j][u] = par[j-1][par[j-1][u]];
inv[j][u] = inv[j-1][u] + inv[j-1][par[j-1][u]];
}
// cout << "at " << u << " val = " << val[u] << " and inv = " << inv[0][u] << endl;
for(auto&e : adj[u]) if(e.first != par[0][u]){
val[e.first] = e.second;
par[0][e.first] = u;
inv[0][e.first] = e.second > val[u];
dis[e.first] = dis[u]+1;
pre(e.first);
}
tout[u] = tt;
}
bool isAnc(int u ,int v){ //is u ancestor of v?
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
int main()
{ int n ,k;
scanf("%d%d",&n,&k);
adj.resize(n+1);
vector <query> qs;
for(int t = 1; t < n+k; t++){
char q; int x ,y;
scanf(" %c%d",&q,&x);
if(q == 'S'){
scanf("%d",&y);
adj[x].push_back({y ,t});
adj[y].push_back({x ,t});
qs.push_back({0 ,t ,x ,y});
}
else if(q == 'Q'){
scanf("%d",&y);
qs.push_back({1 ,t ,x ,y});
}
else
qs.push_back({2 ,t ,x ,-1});
}
memset(par ,-1 ,sizeof par);
par[0][1] = 1;
pre(1);
DSU d(n+1);
for(query&q : qs){
if(q.type == 0){
d.join(q.fr ,q.to);
}
else if(q.type == 1){
if(d.find(q.fr) != d.find(q.to))
printf("no\n");
else{
int a = q.to ,b = q.fr;
for(int j = LOG_N-1; ~j; j--)
if(par[j][a] != -1 && inv[j][a] == 0)
a = par[j][a];
for(int j = LOG_N-1; ~j; j--)
if(par[j][b] != -1 && inv[j][b] == (1<<j))
b = par[j][b];
// cout << q.to << " can reach " << a << endl;
// cout << q.fr << " can reach " << b << endl;
if(dis[a] < dis[b])
swap(a ,b);
a = par[0][a];
int u = q.to ,v = q.fr;
for(int j = LOG_N-1; ~j; j--) if((dis[u]-dis[a]-1)>>j&1)
u = par[j][u];
for(int j = LOG_N-1; ~j; j--) if((dis[v]-dis[a]-1)>>j&1)
v = par[j][v];
// cout << "a = " << a << endl;
// cout << tin[a] << ' ' << tout[a] << endl;
if(isAnc(a ,q.fr) && isAnc(a ,q.to) && val[u] <= val[v])
printf("yes\n");
else
printf("no\n");
}
}
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
servers.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf(" %c%d",&q,&x);
| ~~~~~^~~~~~~~~~~~~~~
servers.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d",&y);
| ~~~~~^~~~~~~~~
servers.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d",&y);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
11568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
11568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
11472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
11472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
11540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
11540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
11480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
11480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
11536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
44 ms |
11536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
11496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
11496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
