Submission #65095

#TimeUsernameProblemLanguageResultExecution timeMemory
65095zscoderCollapse (JOI18_collapse)C++17
100 / 100
9743 ms99964 KiB
#include "collapse.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back typedef long long ll; typedef pair<int,int> ii; typedef vector<int> vi; typedef long double ld; typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds; struct DSU { vector<int> par; vector<int> rank; vector<int> used; void init(int n) { par.clear(); rank.clear(); used.clear(); for(int i=0;i<n;i++) { par.pb(i); rank.pb(1); } } int rt(int u) { if(par[u]==u) return u; else return rt(par[u]); } bool merge(int u, int v) { u=rt(u); v=rt(v); if(u==v) return false; ////cerr<<"MERGE : "<<u<<' '<<v<<'\n'; if(rank[u]<rank[v]) swap(u,v); used.pb(u); used.pb(v); rank[u]+=rank[v]; par[v]=u; return true; } void reset() { for(int v:used) par[v]=v,rank[v]=1; used.clear(); } }; int ans[123456]; const int C = 800; int n; ii rev(ii edge) { return mp(n-1-edge.fi,n-1-edge.se); } bool cmp(ii a, ii b) { if(a.se!=b.se) return a.se<b.se; else return a.fi<b.fi; } void solve(vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query, vector<ii> fixed) { int ptr_fixed = 0; DSU general; general.init(n); DSU specific; specific.init(n); int cc=0; for(auto x:query) { int pos = x.fi; int lab = x.se.fi; while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos) { //cerr<<"MERGE : "<<fixed[ptr_fixed].fi<<' '<<fixed[ptr_fixed].se<<'\n'; cc+=general.merge(fixed[ptr_fixed].fi,fixed[ptr_fixed].se); //amortized O(n) ptr_fixed++; } //O(sqrt(n)) int c=0; for(auto it: *x.se.se) { if(it.se<=pos) { //cerr<<"MERGE : "<<it.fi<<' '<<it.se<<' '<<general.rt(it.fi)<<' '<<general.rt(it.se)<<'\n'; c+=specific.merge(general.rt(it.fi),general.rt(it.se)); } } //cerr<<"CC : "<<lab<<' '<<pos<<' '<<cc+c<<'\n'; ans[lab]+=pos+1-(cc+c); specific.reset(); } } std::vector<int> simulateCollapse( int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y, std::vector<int> W, std::vector<int> P ) { vi answer; answer.resize(int(W.size())); n=N; set<ii> curset; //set of current paths vector<pair<int,ii> > queries; for(int i=0;i<T.size();i++) { if(X[i]>Y[i]) swap(X[i],Y[i]); } for(int i=0;i<W.size();i++) { queries.pb(mp(W[i],mp(P[i],i))); } sort(queries.begin(),queries.end()); int curptr = 0; for(int l=0;l<T.size();l+=C) //O(sqrt(N)) { int r = min(l+C-1,int(T.size())-1); //solve all queries where l<=W<=r set<ii> fixed = curset; //stores the edges that wont be changed this block set<ii> change; //stores the set of edges that will be changed this block for(int i=l;i<=r;i++) change.insert(mp(X[i],Y[i])); set<ii> dynamic; //stores the current progress of the edges changed in this block for(auto edge:change) { if(fixed.find(edge)!=fixed.end()) { fixed.erase(edge); dynamic.insert(edge); } } vector<pair<int,pair<int,shared_ptr<vector<ii> > > > > query1,query2; for(int i=l;i<=r;i++) //O(sqrt(N)) { if(!T[i]) { curset.insert(mp(X[i],Y[i])); dynamic.insert(mp(X[i],Y[i])); } else { curset.erase(mp(X[i],Y[i])); dynamic.erase(mp(X[i],Y[i])); } shared_ptr<vector<ii> > p1(new vector<ii>), p2(new vector<ii>); //shared_ptr new trick acquired for(auto edge:dynamic) //O(sqrt(N)) { p1->pb(edge); p2->pb(mp(rev(edge).se,rev(edge).fi)); } while(curptr<queries.size()&&queries[curptr].fi<=i) { query1.pb(mp(queries[curptr].se.fi,mp(queries[curptr].se.se, p1))); query2.pb(mp(n-2-queries[curptr].se.fi,mp(queries[curptr].se.se, p2))); curptr++; } } sort(query1.begin(),query1.end()); sort(query2.begin(),query2.end()); //hope shared pointer doesn't get sorted vector<ii> fixed2; for(auto x:fixed) fixed2.pb(x); sort(fixed2.begin(),fixed2.end(),cmp); solve(query1, fixed2); for(auto &x:fixed2) {x.fi=n-1-x.fi; x.se=n-1-x.se; swap(x.fi,x.se);} sort(fixed2.begin(),fixed2.end(),cmp); solve(query2, fixed2); } for(int i=0;i<answer.size();i++) answer[i]=ans[i]; return answer; }

Compilation message (stderr)

collapse.cpp: In function 'void solve(std::vector<std::pair<int, std::pair<int, std::shared_ptr<std::vector<std::pair<int, int> > > > > >, std::vector<std::pair<int, int> >)':
collapse.cpp:80:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr_fixed<fixed.size()&&fixed[ptr_fixed].se<=pos)
         ~~~~~~~~~^~~~~~~~~~~~~
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:114:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++)
              ~^~~~~~~~~
collapse.cpp:118:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++)
              ~^~~~~~~~~
collapse.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int l=0;l<T.size();l+=C) //O(sqrt(N))
              ~^~~~~~~~~
collapse.cpp:156:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(curptr<queries.size()&&queries[curptr].fi<=i)
          ~~~~~~^~~~~~~~~~~~~~~
collapse.cpp:173:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<answer.size();i++) answer[i]=ans[i];
              ~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...