#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)
const ll maxn=3e5+10 ;
const ll base=3e18;
const ll mod= 1e9+7 ;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
/// have medal in APIO
/// goal 2/8
char p[maxn];
ll x[maxn];
ll y[maxn];
vector<pll> adj[maxn];
ll siz[maxn];
bool dd[maxn];
ll find_siz(ll u,ll par)
{
siz[u]=1;
for (auto p:adj[u])
{
ll to=p.ff;
if (to==par||dd[to])
continue;
siz[u]+=find_siz(to,u);
}
return siz[u];
}
ll find_cen(ll u,ll par,ll siz1)
{
ll mx=siz1-siz[u];
for (auto p:adj[u])
{
ll to=p.ff;
if (to==par||dd[to])
continue;
mx=max(mx,siz[to]);
ll h=find_cen(to,u,siz1);
if (h!=-1)
{
return h;
}
}
if (mx*2<=siz1)
return u;
return -1;
}
ll fwt[maxn];
ll dd1[maxn];
vector<ll> adjq[maxn];
vector<pll> adjq1[maxn];
ll res[maxn];
bool lf(pll x,pll y)
{
return x.ss<y.ss;
}
void update(ll x,ll diff)
{
for (int i=x; i<maxn; i+= i&(-i))
fwt[i]+=diff;
}
ll get(ll x,ll y)
{
ll ans=0;
for (int i=y; i; i-= i&(-i))
ans+=fwt[i];
for (int i=x-1; i; i-= i&(-i))
ans-=fwt[i];
return ans;
}
void dfsget(ll u,ll par,ll pre,ll mx)
{
for (auto to:adjq1[u])
{
ll id=to.ss;
ll nxt=to.ff;
if (dd1[nxt]&&mx<id&&dd1[nxt]<=id)
{
res[id]=1;
}
}
for (auto p:adjq[u])
{
if (p>=mx)
{
res[p]+=get(1,p);
}
}
for (auto p:adj[u])
{
ll to=p.ff;
ll w=p.ss;
if (dd[to]||to==par)
continue;
if (w<pre)
{
dfsget(to,u,w,mx);
}
}
}
void dfsup(ll u,ll par,ll pre,ll diff,ll t)
{
update(pre,diff);
dd1[u]=t*pre;
for (auto p:adj[u])
{
ll to=p.ff;
ll w=p.ss;
if (dd[to]||to==par)
continue;
if (w>pre)
{
dfsup(to,u,w,diff,t);
}
}
}
void centroid(ll u)
{
ll siz=find_siz(u,0);
sort(adj[u].begin(),adj[u].end(),lf);
ll cen=find_cen(u,0,siz);
update(1,1);
dd1[cen]=1;
// cout <<cen<<" chk1"<<endl;
for (int i=adj[cen].size()-1; i>=0; i--)
{
ll to=adj[cen][i].ff;
if (dd[to])
continue;
// cout <<to<<" "<<adj[cen][i].ss<<" wtf"<<endl;
dfsget(to,cen,adj[cen][i].ss,adj[cen][i].ss);
dfsup(to,cen,adj[cen][i].ss,1,1);
}
dd1[cen]=0;
update(1,-1);
for (auto p:adjq[cen])
{
res[p]+=get(1,p);
}
for (int i=adj[cen].size()-1; i>=0; i--)
{
ll to=adj[cen][i].ff;
if (dd[to])
continue;
dfsup(to,cen,adj[cen][i].ss,-1,0);
}
dd[cen]=1;
// exit(0);
for (auto p:adj[cen])
{
ll to=p.ff;
if (dd[to])
continue;
centroid(to);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
ll n, k;
cin>> n>> k;
k+=n-1;
for (int i=1; i<=k; i++)
{
cin>> p[i];
if (p[i]=='C')
{
cin>> x[i];
adjq[x[i]].pb(i);
}
else
{
cin>> x[i]>> y[i];
if (p[i]=='S')
{
adj[x[i]].pb(make_pair(y[i],i));
adj[y[i]].pb(make_pair(x[i],i));
}
else
{
if (x[i]!=y[i]) adjq1[y[i]].pb(make_pair(x[i],i));
else res[i]=1;
}
}
}
centroid(1);
for (int i=1; i<=k; i++)
{
if (p[i]=='C')
{
cout <<res[i]+1<<endl;
}
else if (p[i]=='Q')
{
if (res[i])
cout <<"yes"<<endl;
else
cout <<"no"<<endl;
}
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
176 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
177 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
28180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
28180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
28372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
28372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
28248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
28248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
28108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
28108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
28224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
28224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
28256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
28256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
