| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1263061 | sasde | Collapse (JOI18_collapse) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "collapse.h"
using namespace std;
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define se second
#define fi first
#define pb push_back
#define emb emplace_back
const int N=1e6+5,block=400;
int index[N];
map<ii,int>M;
bool k[N];
struct DSUrollback {
struct State {
int u, v, rku, rkv, timer,sz;
};
int n,sz;
vector<int> par, rk;
vector<State> history;
DSUrollback() : n(0) {}
DSUrollback(int _n) : n(_n), par(_n + 5), rk(_n + 5, 0) {
history.clear();
sz=0;
for (int i = 1; i <= n; ++i) par[i] = i;
}
void build(int _n) {
*this = DSUrollback(_n);
}
int find(int u) {
while (par[u] != u) u = par[u];
return u;
}
bool join(int u, int v, int timer) {
u = find(u);
v = find(v);
if (u == v) return false;
if (rk[u] < rk[v]) std::swap(u, v);
history.push_back({u, v, rk[u], rk[v], timer,sz});
++sz;
par[v] = u;
if (rk[u] == rk[v]) rk[u]++;
return true;
}
void rollback(int timer) {
while (!history.empty() && history.back().timer >= timer) {
State s = history.back(); history.pop_back();
par[s.u] = s.u;
par[s.v] = s.v;
rk[s.u] = s.rku;
rk[s.v] = s.rkv;
sz=s.sz;
}
}
};
vector<int>up[N],down[N],req[N],upB[N],downB[N];
bool vis[N];
vector<int> simulateCollapse(int node,vector<int>t,vector<int>x,vector<int>y,vector<int>w,vector<int>p){
int query=sz(w),edge=sz(t);
vector<int>ans(query);
vector<int>vitri(query);
iota(all(vitri),0);
sort(all(vitri),[&](int x,int y){
return w[x]<w[y];
});
// for(auto x:vitri)cout <<x<<" ";
for(int i=0;i<edge;++i){
if(x[i]>y[i])swap(x[i],y[i]);
if(t[i]==0)M[{x[i],y[i]}]=i;
else index[i]=M[{x[i],y[i]}];
}
int j=0;
for(int _=0;_<edge;_+=block){
int L=_,R=min(edge-1,_+block-1);
vector<int>del,ups,downs,checku(node,0),checkd(node,0);
while(j<query&&w[vitri[j]]<=R){
req[p[vitri[j]]].emb(vitri[j]);
++j;
}
for(int i=L;i<=R;++i){
if(t[i]==0){
upB[y[i]].emb(i);
downB[x[i]].emb(i);
checkd[x[i]]=1;
checku[y[i]]=1;
// cout <<node<<" "<<x[i]<<" "<<y[i]<<'\n';
}
else if(index[i]<L)del.emb(i),vis[index[i]]=true;;
}
for(int i=0;i<node;++i){
if(checku[i])ups.emb(i);
}
for(int i=node-1;i>=0;--i)
if(checkd[i])downs.emb(i);
DSUrollback dsu(node);
for(int i=0;i<node;++i){
for(int j:up[i])if(!vis[j]){
dsu.join(x[j],y[j],-1);
}
for(int j:req[i]){
for(int k=L;k<=w[j];++k){
if(t[k]==1)vis[index[k]]=true;
}
for(int dele:del){
if(dele<=w[j])continue;
int _dele=index[dele];
if(y[_dele]<=i){
dsu.join(x[_dele],y[_dele],1);
}
}
for(auto k:ups){
if(k>i)break;
for(auto l:upB[k]){
if(!vis[l]&&l<=w[j]){
// cout <<x[l]<<" "<<y[l]<<'\n';
dsu.join(x[l],y[l],1);
}
}
}
// cout <<i+1<<" "<<dsu.sz<<'\n';
ans[j]+=i+1-dsu.sz;
dsu.rollback(1);
for(int k=L;k<=w[j];++k){
if(t[k]==1&&index[k]>=L)vis[index[k]]=false;
}
}
}
dsu.build(node);
for(int i=node-1;i>=0;--i){
for(int j:down[i])if(!vis[j]){
dsu.join(x[j],y[j],-1);
}
for(int j:req[i]){
for(int k=L;k<=w[j];++k){
if(t[k]==1)vis[index[k]]=true;
}
for(int dele:del){
if(dele<=w[j])continue;
int _dele=index[dele];
if(x[_dele]>i){
dsu.join(x[_dele],y[_dele],1);
}
}
for(auto k:downs){
if(k<=i)break;
for(auto l:downB[k]){
if(!vis[l]&&l<=w[j]){
// cout <<x[l]<<" "<<y[l]<<'\n';
dsu.join(x[l],y[l],1);
}
}
}
// cout <<i+1<<" "<<dsu.sz<<'\n';
ans[j]+=node-(i+1)-dsu.sz;
dsu.rollback(1);
for(int k=L;k<=w[j];++k){
if(t[k]==1&&index[k]>=L)vis[index[k]]=false;
}
}
}
for(int i=L;i<=R;++i){
up[y[i]].emb(i);
down[x[i]].emb(i);
}
}
return ans;
}
// main()
// {
// srand(time(0));
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// #define task "xs"
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// int node;
// vector<int>t,x,y,w,q;
// cin >> node;
// int a,b,c;
// while(cin >>a >> b >> c){
// if(!a&&!b&&!c)break;
// t.emb(a);
// x.emb(b);
// y.emb(c);
// // cout <<a<<" "<<b<<" "<<c<<'\n';
// }
// while(cin >> a >> b){
// w.emb(a);
// q.emb(b);
// }
// vector<int>res=simulateCollapse(node,t,x,y,w,q);
// for(auto x:res)cout <<x<<'\n';
// }
/*
3
0 1 2
0 1 3
0 2 3
1 2
2 3
*/