Submission #1114953

#TimeUsernameProblemLanguageResultExecution timeMemory
1114953HoriaHaivasInside information (BOI21_servers)C++14
50 / 100
433 ms47348 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 idk { int type;///0 - update, 1 - query int l; int r; int who; }; bool cmp(idk a, idk b) { if (a.l!=b.l) return a.l>b.l; else return a.r<b.r; } struct edge { int to; int w; }; vector<idk> events; 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); } } int query(int idx) { int ans; ans=0; while (idx>0) { ans+=aib[idx]; idx-=idx&(-idx); } return ans; } 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; } bool canadd; void add_cresc(int node, int parent, int first, int last) { cresc[node]= {first,last}; if (canadd) events.push_back({0,first,last,0}); 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.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 { events.push_back({1,first+1,x.moment-1,x.moment}); } } 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(); events.clear(); recalc(node,-1); centroid=find_centroid(node,-1,sz[node]); globc=centroid; blocked[centroid]=1; canadd=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 { events.push_back({1,1,x.moment-1,x.moment}); } } canadd=0; 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); } } sort(events.begin(),events.end(),cmp); for (auto x : events) { if (x.type==0) { update(x.r,1); } else { q[x.who].ans+=query(x.r)+1; } } for (auto x : events) { if (x.type==0) { update(x.r,-1); } } 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; qq[q[i].u].push_back(q[i]); } } 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 if (q[i].type=='C') { cout << q[i].ans << "\n"; } } }

Compilation message (stderr)

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