#include <bits/stdc++.h>
using namespace std;
const int nx=250005, kx=18, mod=1;
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], lst, 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 idx)
{
if (in[a[idx]]<=in[b[idx]]&&in[b[idx]]<=out[a[idx]]) return {a[idx], 0};
int tmp=a[idx];
for (int i=kx-1; i>=0; i--) if (!(in[pa[tmp][i]]<=in[b[idx]]&&in[b[idx]]<=out[pa[tmp][i]])) tmp=pa[tmp][i];
if (lvl[up[a[idx]]]>lvl[pa[tmp][0]]) return {-1, 0};
return {pa[tmp][0], pw[tmp]};
}
int query(int i)
{
auto [u, lst]=query1(i);
if (u==-1) return 0;
else
{
if (u==b[i]&&lst<=cnt[i]) return 1;
else if (u==b[i]&&lst>cnt[i]) return 0;
else
{
int vl=pw[b[i]], tmp=b[i];
if (lvl[dn[b[i]]]>lvl[u]||pw[b[i]]>cnt[i]) 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);
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)
{
lst=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];
lst=cnt[i];
}
}
if (opr[i]=='Q') cout<<(query(i)?"yes\n":"no\n");
if (opr[i]=='C')
{
int tmp=dp[a[i]];
//cout<<"debug "<<i<<' '<<lst+1<<' '<<cnt[i]<<'\n';
for (int j=lst+1; j<=cnt[i]; j++)
{
int f=1;
b[i]=a[idx[j]];
//cout<<"here "<<i<<' '<<a[i]<<' '<<b[i]<<'\n';
if (!query(i)) f=0;
b[i]=b[idx[j]];
//cout<<"second "<<i<<' '<<a[i]<<' '<<b[i]<<'\n';
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[i]], tmp=b[i];
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
17796 KB |
Output is correct |
| 2 |
Correct |
44 ms |
18004 KB |
Output is correct |
| 3 |
Correct |
57 ms |
18004 KB |
Output is correct |
| 4 |
Correct |
45 ms |
18264 KB |
Output is correct |
| 5 |
Correct |
47 ms |
18344 KB |
Output is correct |
| 6 |
Correct |
71 ms |
18108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
17796 KB |
Output is correct |
| 2 |
Correct |
44 ms |
18004 KB |
Output is correct |
| 3 |
Correct |
57 ms |
18004 KB |
Output is correct |
| 4 |
Correct |
45 ms |
18264 KB |
Output is correct |
| 5 |
Correct |
47 ms |
18344 KB |
Output is correct |
| 6 |
Correct |
71 ms |
18108 KB |
Output is correct |
| 7 |
Incorrect |
24 ms |
17756 KB |
Extra information in the output file |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
17756 KB |
Output is correct |
| 2 |
Execution timed out |
3517 ms |
33208 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
17756 KB |
Output is correct |
| 2 |
Execution timed out |
3517 ms |
33208 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
17756 KB |
Output is correct |
| 2 |
Execution timed out |
3575 ms |
39800 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
17756 KB |
Output is correct |
| 2 |
Execution timed out |
3575 ms |
39800 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
17752 KB |
Output is correct |
| 2 |
Execution timed out |
3584 ms |
33124 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
17752 KB |
Output is correct |
| 2 |
Execution timed out |
3584 ms |
33124 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
17752 KB |
Output is correct |
| 2 |
Execution timed out |
3540 ms |
39756 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
17752 KB |
Output is correct |
| 2 |
Execution timed out |
3540 ms |
39756 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
17752 KB |
Output is correct |
| 2 |
Correct |
53 ms |
18040 KB |
Output is correct |
| 3 |
Correct |
57 ms |
18072 KB |
Output is correct |
| 4 |
Correct |
47 ms |
18012 KB |
Output is correct |
| 5 |
Correct |
54 ms |
18316 KB |
Output is correct |
| 6 |
Correct |
68 ms |
18000 KB |
Output is correct |
| 7 |
Correct |
31 ms |
17752 KB |
Output is correct |
| 8 |
Execution timed out |
3541 ms |
33216 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
17752 KB |
Output is correct |
| 2 |
Correct |
53 ms |
18040 KB |
Output is correct |
| 3 |
Correct |
57 ms |
18072 KB |
Output is correct |
| 4 |
Correct |
47 ms |
18012 KB |
Output is correct |
| 5 |
Correct |
54 ms |
18316 KB |
Output is correct |
| 6 |
Correct |
68 ms |
18000 KB |
Output is correct |
| 7 |
Correct |
31 ms |
17752 KB |
Output is correct |
| 8 |
Execution timed out |
3541 ms |
33216 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
