#include <bits/stdc++.h>
using namespace std;
#define int long long
struct val{
int n, cnt = 0;
vector<vector<array<int, 2>>> g;
vector<array<int, 17>> vu, vd, p;
vector<array<int, 17>> ma, mi;
vector<int> ti, to;
vector<int> d;
val(){};
val(vector<vector<array<int, 2>>> _g){
n = _g.size();
g = _g;
d.resize(n, -1); vu.resize(n);
vd.resize(n); p.resize(n);
ti.resize(n); to.resize(n);
ma.resize(n); mi.resize(n);
dfs(0, 0);
for(int i=1; i<17; i++){
for(int l=0; l<n; l++){
p[l][i] = p[p[l][i-1]][i-1];
}
}
for(int i=1; i<17; i++){
for(int l=0; l<n; l++){
ma[l][i]=max(ma[l][i-1], ma[p[l][i-1]][i-1]);
mi[l][i]=min(mi[l][i-1], mi[p[l][i-1]][i-1]);
if(vu[p[l][i-1]][i-1]<=vu[l][i-1]) vu[l][i] = vu[l][i-1];
else vu[l][i] = 1e18;
if(vd[p[l][i-1]][i-1] >= vd[l][i-1]) vd[l][i] =vd[l][i-1];
else vd[l][i] = 1e18;
}
}
}
void dfs(int v, int par){
d[v] = d[par] +1;
p[v][0]=par; ti[v] = cnt++;
for(auto [i, j]: g[v]){
if(i == par) continue;
vu[i][0] = j; vd[i][0]=j;
ma[i][0]=j; mi[i][0]=j;
dfs(i, v);
}
to[v] = cnt++;
}
auto ia(int a, int b){
return ti[a]<=ti[b] && to[a]>= to[b];
}
int operator()(int x, int y){
if(x==y)return 0;
// 1e18 if no way
// max value of that path
if(ia(x, y)){
int m = 0, lasty;
for(int j=16; j>=0; j--){
if((1<<j) <= d[y] && !ia(y, x)){
if(vd[y][j]==1e18) m = 1e18;
lasty = ma[x][j];
y = p[y][j];
if(lasty>vu[y][0]) m = 1e18;
}
}
if(m!=0) return 1e18;
else return vu[y][0];
}
int m = vu[x][0];
int tmp =m;
int lastx = m, lasty=vu[y][0];
for(int j=16; j>=0; j--){
if((1<<j) <= d[x] && !ia(p[x][j], y)){
m = max(m, vu[x][j]);
lastx = mi[x][j];
x = p[x][j];
if(lastx<vu[x][0]) m = 1e18;
}
if((1<<j) <= d[y] && !ia(p[y][j], x)){
m = max(m, vd[y][j]);
lasty = ma[y][j];
y = p[y][j];
if(lasty>vu[y][0]) m = 1e18;
}
}
if(m != tmp) return 1e18;
if(!ia(x, y)&&(!ia(y, x))){
if(vu[x][0]<vu[y][0]) return 1e18;
}
return m;
}
};
val a;
/*
struct centroid{
};*/
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k; cin >> n >> k;
vector<vector<array<int, 2>>> g(n);
/// a dan b ye erişirkenki max değer
/// a dan b ye erişim var mı
int time = 0;
vector<array<int, 4>> qu;
for(int i=1; i<n+k; i++){
char t; cin >> t;
if (t=='S'){
time++;
int a, b; cin >> a >> b;
a--; b--;
g[a].push_back({b, time});
g[b].push_back({a, time});
}
else if(t=='Q'){
int a, b; cin >> a >> b;
a--; b--;
// can i go from b to a
qu.push_back({0, a, b, time});
}
else{
int a; cin >> a; a--;
qu.push_back({1, a, a, time});
}
}
a = val(g);
for(auto [i, j, k, l]: qu){
if(i==0){
cout<<(a(j, k)<=l?"yes":"no")<<"\n";
}
}
// centroid c(g);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
6352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
6352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
6356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
6356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
5072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
4816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
4816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
6096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
