#include <bits/stdc++.h>
using namespace std;
const int nx=250005, kx=18, mod=400;
int n, k, a[nx], b[nx], idx[nx], cnt[nx], lvl[nx], pa[nx][kx], up[nx], dn[nx], pw[nx], t, in[nx], out[nx], lstupd, dp[nx], l[nx], r[nx], pts[nx];
char opr[nx];
vector<pair<int, int>> d[nx];
void dfs(int u, int p)
{
lvl[u]=lvl[p]+1;
in[u]=++t;
up[u]=p;
if (pw[u]<pw[p]) up[u]=up[p];
dn[u]=p;
if (pw[u]>pw[p]) dn[u]=dn[p];
pa[u][0]=p;
for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
for (auto [v, w]:d[u]) if (v!=p) pw[v]=w, dfs(v, u);
out[u]=t;
}
pair<int, int> query1(int id)
{
if (in[a[id]]<=in[b[id]]&&in[b[id]]<=out[a[id]]) return {a[id], 0};
int tmp=a[id];
for (int i=kx-1; i>=0; i--) if (!(in[pa[tmp][id]]<=in[b[id]]&&in[b[id]]<=out[pa[tmp][id]])) tmp=pa[tmp][id];
if (lvl[up[a[id]]]>lvl[pa[tmp][0]]) return {-1, 0};
return {pa[tmp][0], pw[tmp]};
}
int query(int id)
{
auto [u, lst]=query1(id);
if (u==-1) return 0;
else
{
if (u==b[id]&&lst<=cnt[id]) return 1;
else if (u==b[id]&&lst>cnt[id]) return 0;
else
{
int vl=pw[b[id]], tmp=b[id];
if (lvl[dn[b[id]]]>lvl[u]||pw[b[id]]>cnt[id]) return 0;
else
{
for (int j=kx-1; j>=0; j--) if (lvl[pa[tmp][j]]>lvl[u]) tmp=pa[tmp][j];
if (lst<pw[tmp]) return 1;
else return 0;
}
}
}
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
//freopen("server.in","r",stdin);
//freopen("server.out","w",stdout);
cin>>n>>k;
for (int i=1; i<=n; i++) pts[i]=i, dp[i]=1;
for (int i=1; i<n+k; i++)
{
cin>>opr[i];
cnt[i]=cnt[i-1];
if (opr[i]=='S') cin>>a[i]>>b[i], idx[++cnt[i]]=i, d[a[i]].push_back({b[i], cnt[i]}), d[b[i]].push_back({a[i], cnt[i]}), l[cnt[i]+n]=pts[a[i]], r[cnt[i]+n]=pts[b[i]], pts[a[i]]=pts[b[i]]=cnt[i]+n;
if (opr[i]=='Q') cin>>b[i]>>a[i];
if (opr[i]=='C') cin>>a[i];
}
dfs(1, 1);
for (int i=1; i<n+k; i++)
{
if (opr[i]=='S')
{
if ((cnt[i]%mod)==0)
{
lstupd=cnt[i];
for (int j=1; j<=n+cnt[j]; j++) dp[j]=1;
for (int j=n+cnt[i]; j>=n+1; j--) dp[l[j]]+=dp[j], dp[r[j]]+=dp[j];
lstupd=cnt[i];
}
}
if (opr[i]=='Q') cout<<(query(i)?"yes\n":"no\n");
if (opr[i]=='C')
{
int tmp=dp[a[i]];
for (int j=lstupd+1; j<=cnt[i]; j++)
{
int f=1;
b[i]=a[idx[j]];
if (!query(i)) f=0;
b[i]=b[idx[j]];
if (!query(i)) f=0;
tmp+=f;
}
cout<<tmp<<'\n';
}
}
}
Compilation message
servers.cpp: In function 'int query(int)':
servers.cpp:44:17: warning: unused variable 'vl' [-Wunused-variable]
44 | int vl=pw[b[id]], tmp=b[id];
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
23 ms |
9052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
23 ms |
9052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
22 ms |
9056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
22 ms |
9056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
9052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
9052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
9056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
9056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
9048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
21 ms |
9048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
27 ms |
9048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
27 ms |
9048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
