Submission #1114424

#TimeUsernameProblemLanguageResultExecution timeMemory
1114424HoriaHaivasInside information (BOI21_servers)C++14
2.50 / 100
284 ms39096 KiB
/* "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 && 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 (stderr)

servers.cpp: In function 'int main()':
servers.cpp:159:15: warning: unused variable 'j' [-Wunused-variable]
  159 |     int n,k,i,j;
      |               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...