/*
"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 edge
{
int to;
int w;
};
operatie q[240005];
vector<operatie> qq[120005];
map<int,pair<int,int>> cresc;
//vector<int> aib;
vector<edge> nodes[120005];
bool blocked[120005];
int sz[120005];
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};
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)
{
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.u==x.v)
q[x.moment].ans|=1;
else if (x.u==globc && parent==globc && last<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;
}
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 last)
{
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.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;
}
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])
{
cd(x.to,centroid);
}
}
}
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;
}
}
cd(1,0);
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";
}
}
}
Compilation message
servers.cpp: In function 'int main()':
servers.cpp:159:15: warning: unused variable 'j' [-Wunused-variable]
159 | int n,k,i,j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
20968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
20968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
20884 KB |
Output is correct |
| 2 |
Correct |
252 ms |
39096 KB |
Output is correct |
| 3 |
Correct |
261 ms |
39100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
20884 KB |
Output is correct |
| 2 |
Correct |
252 ms |
39096 KB |
Output is correct |
| 3 |
Correct |
261 ms |
39100 KB |
Output is correct |
| 4 |
Incorrect |
23 ms |
20528 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
20716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
20716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
20460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
20460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
20972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
20972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
19692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
