Submission #1114925

#TimeUsernameProblemLanguageResultExecution timeMemory
1114925HoriaHaivasInside information (BOI21_servers)C++14
50 / 100
514 ms46840 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 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 (stderr)

servers.cpp: In function 'int main()':
servers.cpp:224:15: warning: unused variable 'j' [-Wunused-variable]
  224 |     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...