Submission #268728

#TimeUsernameProblemLanguageResultExecution timeMemory
268728MKopchevCollapse (JOI18_collapse)C++14
100 / 100
9334 ms28532 KiB
#include "collapse.h" #include<bits/stdc++.h> using namespace std; const int nmax=1e5+42; int n; vector< pair<int/*cut*/,int/*id*/> >seen[nmax]; set< pair<int,int> > edges; int parent[nmax],sz[nmax]; int root(int node) { while(parent[node]!=node)node=parent[node]; return node; } pair<int/*big*/,int/*small*/> mem[nmax]; int pointer=0; void my_merge(int u,int v) { /* cout<<"my_merge "<<u<<" "<<v<<endl; for(int i=0;i<n;i++)cout<<root(i)<<" ";cout<<endl; */ u=root(u); v=root(v); if(u==v)return; if(sz[u]<sz[v])swap(u,v); mem[pointer]={u,v}; pointer++; parent[v]=u; sz[u]+=sz[v]; } vector<int> other_edge[nmax]; void init() { for(int i=0;i<n;i++) { sz[i]=1; parent[i]=i; other_edge[i]={}; } pointer=0; } set<pair<int,int> > forced,cut; struct info { int cut_line,when,id; }; vector<info> active={}; bool cmp(info a,info b) { return a.cut_line<b.cut_line; } bool cmp_2(info a,info b) { return a.cut_line>b.cut_line; } void pop_pointer(int to) { while(pointer>to) { pointer--; sz[mem[pointer].first]-=sz[mem[pointer].second]; parent[mem[pointer].second]=mem[pointer].second; } } 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) { n=N; for(int i=0;i<W.size();i++) seen[W[i]].push_back({P[i],i}); int C=T.size(); for(int i=0;i<C;i++) if(X[i]>Y[i])swap(X[i],Y[i]); vector<int> outp(W.size(),N); int BLOCK_SIZE=sqrt(C)+1; for(int i=0;i<C;i+=BLOCK_SIZE) { init(); int STOP=T.size()-1; STOP=min(STOP,i+BLOCK_SIZE-1); forced=edges; cut={}; for(int j=i;j<=STOP;j++) if(T[j]==1&&forced.count({X[j],Y[j]})) { forced.erase({X[j],Y[j]}); cut.insert({X[j],Y[j]}); } /* cout<<"forced: "<<endl; for(auto k:forced)cout<<k.first<<" "<<k.second<<endl; cout<<"---"<<endl; */ active={}; for(int t=i;t<=STOP;t++) for(auto k:seen[t]) { info cur; cur.cut_line=k.first; cur.id=k.second; cur.when=t; active.push_back(cur); } sort(active.begin(),active.end(),cmp); for(auto k:forced) other_edge[k.second].push_back(k.first); int j=-1; for(auto k:active) { while(j<k.cut_line) { j++; for(auto p:other_edge[j]) my_merge(p,j); } set< pair<int,int> > cur_cut=cut; for(int j=i;j<=k.when;j++) if(T[j]==0)cur_cut.insert({X[j],Y[j]}); else cur_cut.erase({X[j],Y[j]}); /* cout<<k.cut_line<<" "<<k.when<<" "<<k.id<<" j= "<<j<<endl; cout<<"cur_cut: "<<endl; for(auto p:cur_cut)cout<<p.first<<" "<<p.second<<endl; */ int mem_pointer=pointer; for(auto p:cur_cut) if(p.first<=k.cut_line&&p.second<=k.cut_line) my_merge(p.first,p.second); /* cout<<"pointer= "<<pointer<<endl; cout<<"---"<<endl; */ outp[k.id]-=pointer; pop_pointer(mem_pointer); } /* cout<<i<<" : "<<endl; for(auto k:edges)cout<<k.first<<" "<<k.second<<endl; */ init(); sort(active.begin(),active.end(),cmp_2); for(auto k:forced) other_edge[k.first].push_back(k.second); //cout<<"---\n---\n---\n"<<endl; j=n; for(auto k:active) { while(j-1>k.cut_line) { j--; for(auto p:other_edge[j]) my_merge(p,j); } set< pair<int,int> > cur_cut=cut; for(int j=i;j<=k.when;j++) if(T[j]==0)cur_cut.insert({X[j],Y[j]}); else cur_cut.erase({X[j],Y[j]}); /* cout<<k.cut_line<<" "<<k.when<<" "<<k.id<<" j= "<<j<<endl; cout<<"cur_cut: "<<endl; for(auto p:cur_cut)cout<<p.first<<" "<<p.second<<endl; */ int mem_pointer=pointer; for(auto p:cur_cut) if(p.first>k.cut_line&&p.second>k.cut_line) my_merge(p.first,p.second); /* cout<<"pointer= "<<pointer<<endl; cout<<"---"<<endl; */ outp[k.id]-=pointer; pop_pointer(mem_pointer); } for(int j=i;j<=STOP;j++) if(T[j]==0)edges.insert({X[j],Y[j]}); else edges.erase({X[j],Y[j]}); } return outp; } /* int main() { int N, C, Q; scanf("%d%d%d", &N, &C, &Q); std::vector<int> T(C), X(C), Y(C); for(int i = 0; i < C; i++) { scanf("%d%d%d", &T[i], &X[i], &Y[i]); } std::vector<int> W(Q), P(Q); for(int i = 0; i < Q; i++) { scanf("%d%d", &W[i], &P[i]); } auto res = simulateCollapse(N, T, X, Y, W, P); for(auto i : res) { printf("%d\n", i); } } */

Compilation message (stderr)

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:95:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int i=0;i<W.size();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...