Submission #1189020

#TimeUsernameProblemLanguageResultExecution timeMemory
1189020alexddCollapse (JOI18_collapse)C++20
5 / 100
15091 ms34888 KiB
#include "collapse.h" #include<bits/stdc++.h> using namespace std; int n; const int BUC = 320; struct DSU { int father[100005],siz[100005]; vector<pair<pair<int,int>,int>> history; void init() { history.clear(); for(int i=0;i<n;i++) father[i]=i, siz[i]=1; } int gas(int x) { if(father[x]!=x) return gas(father[x]); return x; } void unite(int x, int y) { x = gas(x); y = gas(y); if(x==y) return; history.push_back({{y,father[y]},0}); history.push_back({{x,siz[x]},1}); father[y] = x; siz[x] += siz[y]; } int get_time() { return history.size(); } void rollback(int t) { while((int)history.size() > t) { if(history.back().second == 0) father[history.back().first.first] = history.back().first.second; else siz[history.back().first.first] = history.back().first.second; history.pop_back(); } } }; vector<pair<int,int>> begin_on_t[100005],end_on_t[100005]; vector<pair<int,pair<int,int>>> begin_on_poz[100005],end_on_poz[100005]; vector<pair<pair<int,int>,pair<int,int>>> edges; void add_edge(int tle, int tri, int x, int y) { assert(tle<=tri); assert(x<=y); edges.push_back({{tle,tri},{x,y}}); begin_on_t[tle].push_back({x,y}); end_on_t[tri].push_back({x,y}); begin_on_poz[x].push_back({y,{tle,tri}}); end_on_poz[y].push_back({x,{tle,tri}}); } vector<pair<pair<int,int>,int>> qrys[100005]; bool cmp_edge(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y) { return x.second.second < y.second.second; } bool cmp_edge2(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y) { return x.second.first > y.second.first; } bool cmp_qry(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y) { return x.first.second < y.first.second; } vector<int> sol; void solve(int maxb) { /*sort(edges.begin(),edges.end(),cmp_edge); for(int b=0;b<=maxb;b++) { DSU dsu; dsu.init(); int ble = b*BUC, bri = (b+1)*BUC - 1; sort(qrys[b].begin(),qrys[b].end(),cmp_qry); vector<pair<pair<int,int>,pair<int,int>>> base_edges,special_edges; for(auto [t,e]:edges) { if(t.first <= ble && bri <= t.second) base_edges.push_back({t,e}); else special_edges.push_back({t,e}); } int poz_base=0; for(auto [q,id]:qrys[b]) { int w = q.first, p = q.second; while(poz_base < base_edges.size() && base_edges[poz_base].second.second <= p) { dsu.unite(base_edges[poz_base].second.first, base_edges[poz_base].second.second); poz_base++; } int old_t = dsu.get_time(); for(auto [t,e]:special_edges) if(t.first <= w && w <= t.second && e.second <= p) dsu.unite(e.first, e.second); sol[id] += dsu.get_time()/2; dsu.rollback(old_t); } }*/ for(int b=0;b<=maxb;b++) { for(auto [q,id]:qrys[b]) { int w = q.first, p = q.second; DSU dsu; dsu.init(); for(auto [t,e]:edges) if(t.first <= w && w <= t.second && e.second <= p) dsu.unite(e.first, e.second); sol[id] += dsu.get_time()/2; } } sort(edges.begin(),edges.end(),cmp_edge2);///------------------------------------ for(int b=0;b<=maxb;b++) { for(auto [q,id]:qrys[b]) { int w = q.first, p = q.second; DSU dsu; dsu.init(); for(auto [t,e]:edges) if(t.first <= w && w <= t.second && e.first > p) dsu.unite(e.first, e.second); sol[id] += dsu.get_time()/2; } } } 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; map<pair<int,int>,int> construction_day; for(int i=0;i<T.size();i++) { if(X[i] > Y[i]) swap(X[i],Y[i]); if(T[i]==0) { construction_day[{X[i],Y[i]}] = i; } else { add_edge(construction_day[{X[i],Y[i]}],i-1,X[i],Y[i]); construction_day[{X[i],Y[i]}] = -1; } } for(auto it:construction_day) { if(it.second != -1) { add_edge(it.second, (int)T.size() + 2, it.first.first, it.first.second); } } for(int i=0;i<W.size();i++) qrys[W[i]/BUC].push_back({{W[i],P[i]},i}); sol.resize((int)W.size(),0); solve(T.size()/BUC); for(int i=0;i<W.size();i++) sol[i] = n - sol[i]; return sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...