| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1254664 | minhpk | Collapse (JOI18_collapse) | C++20 | 0 ms | 0 KiB |
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int a,b,c;
vector<int> t;
vector<int> z;
vector<int> z1;
vector<int> w;
vector<int> w1;
vector <int> res;
map<pair<int,int>,int> m;
struct edge{
int x,y,l,r;
};
vector <edge> vec;
vector <pair<int,int>> pos[1000005];
bool cmp(pair<int,int> a,pair<int,int> b){
return max(a.first,a.second)<max(b.first,b.second);
}
bool cmp(pair<int,int> a,pair<int,int> b){
return min(a.first,a.second)>min(b.first,b.second);
}
struct ST{
int f[4000005]={0};
int lazy[4000005]={0};
void build(int id,int l,int r){
lazy[id]=0;
if (l==r){
f[id]=0;
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
f[id]=f[id*2]+f[id*2+1];
}
void push(int id){
if (lazy[id]!=0){
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
f[id*2]+=lazy[id];
f[id*2+1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int x,int y,int val){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
f[id]+=val;
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
push(id);
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
f[id]=f[id*2]+f[id*2+1];
}
int get(int id,int l,int r,int pos){
if (l==r){
return f[id];
}
int mid=(l+r)/2;
push(id);
if (pos<=mid){
return get(id*2,l,mid,pos);
}else{
return get(id*2+1,mid+1,r,pos);
}
}
};
ST f1;
vector<pair<int,int>> f[4000005];
void update(int id,int l,int r,int x,int y,pair<int,int> val){
if (x>r || y<l){
return;
}
if (l>=x && y>=r){
f[id].push_back(val);
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,x,y,val);
update(id*2+1,mid+1,r,x,y,val);
}
int par[1000005];
int sz[1000005];
stack<pair<pair<int,int>,int>> st;
int find(int u){
if (par[u]==u){
return u;
}
return find(par[u]);
}
bool join(int x,int y,int id){
x=find(x);
y=find(y);
if (x==y){
return false;
}
if (sz[x]<sz[y]){
swap(x,y);
}
st.push({{x,sz[x]},id});
st.push({{y,sz[y]},id});
par[y]=x;
sz[x]+=sz[y];
return true;
}
void rollback(int id,int type){
while (st.size() && st.top().second==id){
int x=st.top().first;
int p=st.top().second;
sz[x]=p;
par[x]=x;
st.pop();
int y=st.top().first;
p=st.top().second;
sz[y]=p;
par[y]=y;
st.pop();
if (type==1){
int pre=max(x,y);
f1.update(1,0,a,pre,a,1);
}else{
int pre=min(x,y);
f1.update(1,0,a,0,pre,1);
}
}
}
void dfs(int id,int l,int r){
sort(f[id].begin(),f[id].end(),cmp);
for (auto p:f[id]){
int x=min(p.first,p.second);
if (join(p.first,p.second)){
f1.update(1,0,a,0,x,-1);
}
}
if (l==r){
for (auto p:pos[l]){
int pre=p.second;
int x=p.first;
res[pre]+=f1.get(1,0,a,x);
}
return;
}
int mid=(l+r)/2;
dfs1(id*2,l,mid);
dfs1(id*2+1,mid+1,r);
rollback(id,1);
}
void dfs1(int id,int l,int r){
sort(f[id].begin(),f[id].end(),cmp1);
for (auto p:f[id]){
int x=max(p.first,p.second);
if (join(p.first,p.second)){
f1.update(1,0,a,x,a,-1);
}
}
if (l==r){
for (auto p:pos[l]){
int pre=p.second;
int x=p.first;
res[pre]+=f1.get(1,0,a,x);
}
return;
}
int mid=(l+r)/2;
dfs1(id*2,l,mid);
dfs1(id*2+1,mid+1,r);
rollback(id,2);
}
vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
a=N;
t=T;
z=X;
z1=Y;
w=W;
w1=P;
b=t.size();
c=w.size();
res.resize(c,0);
for (int i=1;i<=b;i++){
int x=z[i-1];
int y=z1[i-1];
int type=t[i-1];
if (type==0){
m[{x,y}]=i;
m[{y,x}]=i;
}else{
vec.push_back({x,y,m[{x,y}],i-1});
m[{x,y}]=0;
m[{y,x}]=0;
}
}
for (auto p:m){
if (p.second!=0){
vec.push_back({p.first.first,p.first.second,p.second,b});
}
}
for (auto p:vec){
auto [x,y,l,r]=p;
pair<int,int> pre={x,y};
update(1,1,b,l,r,pre);
}
for (int i=0;i<c;i++){
int w=w[i];
int p=w1[i];
pos[w+1].push_back({p,i});
}
f1.build(1,0,a);
for (int i=1;i<a;i++){
f1.update(1,0,a,i,a,1);
}
for (int i=0;i<=a;i++){
par[i]=i;
sz[i]=1;
}
dfs(1,1,b);
f1.build(1,0,a);
for (int i=0;i<=a;i++){
par[i]=i;
sz[i]=1;
}
while (st.size()){
st.pop();
}
for (int i=a-1;i>=0;i--){
f1.update(1,0,a,0,i,1);
}
dfs1(1,1,b);
return res;
}