/*
"care a facut teste cu Lattice reduction attack e ciudat"
"linistiti va putin"
- 2023 -
*/
#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
struct operatie
{
char type;
int u;
int v;
int moment;
int ans;
};
struct queque
{
int l;
int r;
};
struct edge
{
int to;
int w;
};
operatie q[240005];
vector<operatie> qq[120005];
map<int,pair<int,int>> cresc;
int aib[240005];
vector<edge> nodes[120005];
bool blocked[120005];
int sz[120005];
int maxx;
void update(int idx, int delta)
{
while (idx<=maxx)
{
aib[idx]+=delta;
idx+=idx&(-idx);
}
}
void update(int l, int r, int delta)
{
update(l,delta);
update(r+1,-delta);
}
int query(int idx)
{
int ans;
ans=0;
while (idx>0)
{
ans+=aib[idx];
idx-=idx&(-idx);
}
return ans;
}
int query(int l, int r)
{
return query(r)-query(l-1);
}
void recalc(int node, int parent)
{
sz[node]=1;
for (auto x : nodes[node])
{
if (x.to!=parent && !blocked[x.to])
{
recalc(x.to,node);
sz[node]+=sz[x.to];
}
}
}
int find_centroid(int node, int parent, int compsize)
{
for (auto x : nodes[node])
{
if (x.to!=parent && !blocked[x.to] && sz[x.to]>compsize/2)
{
return find_centroid(x.to,node,compsize);
}
}
return node;
}
void add_cresc(int node, int parent, int first, int last)
{
cresc[node]= {first,last};
update(first,last,1);
for (auto x : nodes[node])
{
if (x.to!=parent && !blocked[x.to] && x.w>last)
{
add_cresc(x.to,node,first,x.w);
}
}
}
void rem_cresc(int node, int parent, int first, int last)
{
update(first,last,-1);
cresc[node]= {-1,-1};
for (auto x : nodes[node])
{
if (x.to!=parent && !blocked[x.to] && x.w>last)
{
rem_cresc(x.to,node,first,x.w);
}
}
}
int globc;
void solve(int node, int parent, int first, int last)
{
for (auto x : qq[node])
{
if (x.type=='Q')
{
if (x.u==x.v)
q[x.moment].ans|=1;
else if (x.u==globc && first<x.moment)
q[x.moment].ans|=1;
else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
q[x.moment].ans|=0;
else if (cresc[x.u].first>first && cresc[x.u].second<x.moment)
q[x.moment].ans|=1;
}
else
{
}
}
for (auto x : nodes[node])
{
if (x.to!=parent && !blocked[x.to] && x.w<last)
{
solve(x.to,node,first,x.w);
}
}
}
void cd(int node)
{
int centroid;
cresc.clear();
recalc(node,-1);
centroid=find_centroid(node,-1,sz[node]);
globc=centroid;
blocked[centroid]=1;
for (auto x : nodes[centroid])
{
if (!blocked[x.to])
{
add_cresc(x.to,centroid,x.w,x.w);
}
}
for (auto x : qq[centroid])
{
if (x.type=='Q')
{
if (x.u==x.v)
q[x.moment].ans|=1;
else if (cresc.find(x.u)==cresc.end() || (cresc[x.u].first==-1 && cresc[x.u].second==-1))
q[x.moment].ans|=0;
else if (cresc[x.u].second<x.moment)
q[x.moment].ans|=1;
}
else
{
}
}
for (auto x : nodes[centroid])
{
if (!blocked[x.to])
{
rem_cresc(x.to,centroid,x.w,x.w);
solve(x.to,centroid,x.w,x.w);
add_cresc(x.to,centroid,x.w,x.w);
}
}
for (auto x : nodes[centroid])
{
if (!blocked[x.to])
{
rem_cresc(x.to,centroid,x.w,x.w);
}
}
for (auto x : nodes[centroid])
{
if (!blocked[x.to])
{
cd(x.to);
}
}
}
signed main()
{
/*
ifstream fin("secvp.in");
ofstream fout("secvp.out");
*/
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,k,i,j;
cin >> n >> k;
for (i=1; i<=n+k-1; i++)
{
cin >> q[i].type;
q[i].moment=i;
if (q[i].type=='S')
{
cin >> q[i].u >> q[i].v;
nodes[q[i].u].push_back({q[i].v,i});
nodes[q[i].v].push_back({q[i].u,i});
}
if (q[i].type=='Q')
{
cin >> q[i].u >> q[i].v;
qq[q[i].v].push_back(q[i]);
}
if (q[i].type=='C')
{
cin >> q[i].u;
}
}
maxx=n+k-1;
cd(1);
for (i=1; i<=n+k-1; i++)
{
if (q[i].type=='Q')
{
if (q[i].ans==1)
cout << "yes\n";
else
cout << "no\n";
}
else
{
cout << q[i].ans << "\n";
}
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:224:15: warning: unused variable 'j' [-Wunused-variable]
224 | int n,k,i,j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
23012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
23020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
22916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
22916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
