This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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, 18>> vu, vd, p;
vector<array<int, 18>> 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<18; i++){
for(int l=0; l<n; l++){
p[l][i] = p[p[l][i-1]][i-1];
}
}
for(int i=1; i<18; 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(mi[l][i-1]>=ma[p[l][i-1]][i-1]&&vu[p[l][i-1]][i-1]!=1e18) vu[l][i] = vu[l][i-1];
else vu[l][i] = 1e18;
if(ma[l][i-1]<=mi[p[l][i-1]][i-1]&&vd[p[l][i-1]][i-1]!=1e18) 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;
int tmpy=y;
for(int j=17; j>=0; j--){
if((1<<j) <= d[y] && d[y]-(1<<j)>=d[x]){
if(vd[y][j]==1e18) m = 1e18;
lasty = ma[y][j];
m = max(m, ma[y][j]);
y = p[y][j];
if(lasty>vu[y][0]&&y!=x) m = 1e18;
}
}
if(m==1e18) return 1e18;
else return m;
}
int m = vu[x][0];
int tmp =m;
int lastx = m, lasty=vu[y][0];
for(int j=17; 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 = 1;
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){
if(a(j, k)<=l) cout<<"yes\n";
else cout<<"no\n";
}
}
// centroid c(g);
}
Compilation message (stderr)
servers.cpp: In member function 'long long int val::operator()(long long int, long long int)':
servers.cpp:71:17: warning: unused variable 'tmpy' [-Wunused-variable]
71 | int tmpy=y;
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |