// Inside Information
/*
how to solve queries of is A at B:
basically we can just note that
we are looking at at a tree, find LCA of (A, B)
A has to be decreasing to whatever value we care about
B has to be increasing , max has to be less than time of query
O(nLOGn) or even constant with the other version of LCA that i dont know how to code
also be careful of special cases on the LCA
how to solve the other kind of queries
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ROF(i, a, b) for(int i=b-1; i>=a; i--)
#define F0R(i, n) FOR(i, 0, n)
#define R0F(i, n) ROF(i, 0, n)
#define f first
#define s second
#define pb push_back
#define siz(x) (int)x.size()
#define ar array
const int mxN=2.4e5+10;
const int LG=20;
int n, q;
ar<int, 3> qq[mxN];
vector<pair<int, int>> adj[mxN];
int depth[mxN];
int anc[mxN][LG];
int mx[mxN][LG];
int mX[mxN], mN[mxN];
template<class T>void ckmax(T&A, T B){
A=max(A, B);
}
void dfs(int u, int p, int c=-1){
anc[u][0]=p; mx[u][0]=c;
FOR(i, 1, LG){
if(anc[u][i-1]==-1) anc[u][i]=-1, mx[u][i]=-1;
else anc[u][i]=anc[anc[u][i-1]][i-1], mx[u][i]=max(mx[u][i-1], mx[anc[u][i-1]][i-1]);
}
for(auto[v, w]:adj[u]){
if(v==p) continue;
depth[v]=depth[u]+1;
dfs(v, u, w);
}
}
void dfs2(int u, int p, int L, int MX, int MN){
mX[u]=MX, mN[u]=MN;
for(auto[v, w]:adj[u]){
if(v==p) continue;
int nx=MX, ny=MN;
if(w<L) nx=depth[u];
if(w>L) ny=depth[u];
dfs2(v, u, w, nx, ny);
}
}
pair<int, int> lft(int u, int d){
int maxx=0;
for(int i=0; i<LG; i++){
if(d&(1<<i)) ckmax(maxx, mx[u][i]), u=anc[u][i];
}
return {u, maxx};
}
pair<int, int> lca(int X, int Y){
if(depth[X]<depth[Y]) swap(X, Y);
auto[XXX, maxx]=lft(X, depth[X]-depth[Y]);
X=XXX;
if(X==Y) return {X, maxx};
R0F(i, LG){
if(anc[X][i]!=anc[Y][i]){
ckmax(maxx, mx[X][i]);
ckmax(maxx, mx[Y][i]);
X=anc[X][i]; Y=anc[Y][i];
}
}
ckmax(maxx, mx[X][0]);
ckmax(maxx, mx[Y][0]);
return {anc[X][0], maxx};
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
F0R(i, n+q-1){
char T; cin >> T;
if(T=='S'){
int X, Y; cin >> X >> Y; X--; Y--;
adj[X].pb({Y, i});
adj[Y].pb({X, i});
qq[i]={1, X, Y};
}
else if(T=='Q'){
int A, B; cin >> A >> B; A--; B--;
qq[i]={2, A, B};
}
else{
assert(false);
int C; cin >> C; C--;
qq[i]={3, C, -1};
}
}
dfs(0, -1);
dfs2(0, -1, 0, 0, 0);
// F0R(i, n){
// // cout << mx[i][0] << ' ';
// cout << mX[i] << ' ' << mN[i] << "\n";
// }
// cout << "\n";
F0R(i, n+q-1){
if(qq[i][0]==2){
int A=qq[i][1], B=qq[i][2];
swap(A, B);
auto[L, V]=lca(A, B);
// cout << A << ' ' << B << ' ' << L << ' ' << V << ' ' << i << "\n";
if(V>i){
cout << "no\n";
continue;
}
if(mN[A]<=depth[L]&&mX[B]<=depth[L]){
if(A==L||B==L){
cout << "yes\n";
}
else{
int AA=lft(A, depth[L]-depth[A]-1).f, BB=lft(B, depth[L]-depth[B]-1).f;
if(mx[AA][0]<mx[BB][0]) cout << "yes\n";
else cout << "no\n";
}
}
else
cout << "no\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
7748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
7748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
7676 KB |
Output is correct |
| 2 |
Correct |
182 ms |
45832 KB |
Output is correct |
| 3 |
Correct |
177 ms |
45888 KB |
Output is correct |
| 4 |
Correct |
194 ms |
45764 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
7676 KB |
Output is correct |
| 2 |
Correct |
182 ms |
45832 KB |
Output is correct |
| 3 |
Correct |
177 ms |
45888 KB |
Output is correct |
| 4 |
Correct |
194 ms |
45764 KB |
Output is correct |
| 5 |
Runtime error |
12 ms |
12020 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
7728 KB |
Output is correct |
| 2 |
Correct |
181 ms |
45828 KB |
Output is correct |
| 3 |
Correct |
192 ms |
45812 KB |
Output is correct |
| 4 |
Correct |
204 ms |
45828 KB |
Output is correct |
| 5 |
Incorrect |
38 ms |
8624 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
7728 KB |
Output is correct |
| 2 |
Correct |
181 ms |
45828 KB |
Output is correct |
| 3 |
Correct |
192 ms |
45812 KB |
Output is correct |
| 4 |
Correct |
204 ms |
45828 KB |
Output is correct |
| 5 |
Incorrect |
38 ms |
8624 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
7744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
7744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
