| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1256125 | minhpk | Collapse (JOI18_collapse) | C++20 | 0 ms | 0 KiB |
#include 'collapse.h'
#include <bits/stdc++.h>
using namespace std;
int a,b,c;
struct dsu{
int par[1000005];
int sz[1000005];
int cnt;
vector <pair<int,int>> st;
void init(){
cnt=0;
for (int i=1;i<=a;i++){
par[i]=i;
sz[i]=1;
}
}
int find(int u){
if (par[u]==u){
return u;
}
return find(par[u]);
}
void join(int x,int y){
x=find(x);
y=find(y);
if (x==y){
st.push_back({-1,-1});
}
if (sz[x]<sz[y]){
swap(x,y);
}
st.push_back({x,y});
par[y]=x;
sz[x]+=sz[y];
cnt++;
}
void rollback(){
auto [x,y] =st.back();
st.pop_back();
if (x==-1){
return;
}
cnt--;
par[y]=y;
sz[x]-=sz[y];
}
};
dsu d;
int block=320;
vector <int> q[1000005];
set<pair<int,int>> s;
vector <pair<int,int>> v[1000005];
vector<int> pos[1000005];
vector <int> z[1000005];
vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
a=N;
b=T.size();
c=W.size();
vector <int> res(c,0);
for (int i=0;i<c;i++){
q[W[i]].push_back(i);
}
for (int t=0;t<b;t+=block){
set<pair<int,int>> s1;
for (int i=t;i<min(t+block,b);i++){
int x=X[i];
int y=Y[i];
if (x>y){
swap(x,y);
}
if (s.find({x,y})!=s.end()){
s.erase({x,y});
s1.insert({x,y});
}
}
for (int i=t;i<min(t+block,b);i++){
int x=X[i];
int y=Y[i];
if (x>y){
swap(x,y);
}
if (T[i]){
s1.erase({x,y});
}else{
s1.insert({x,y});
}
for (auto p:s1){
v[i].push_back(p);
}
for (auto p:q[i]){
pos[P[p]].push_back(p);
}
}
d.init();
for (int i=0;i<=a;i++){
z[i].clear();
}
for (auto p:s){
z[p.second].push_back(p.first);
}
for (int i=0;i<a;i++){
for (auto p:z[i]){
d.join(p,i);
}
for (auto p:pos[i]){
for (auto j:v[W[p]]){
if (j.second<=P[p]){
d.join(j.first,j.second);
}
}
res[p]+=d.cnt;
for (auto j:v[W[p]]){
if (j.second<=P[p]){
d.rollback();
}
}
}
}
d.init();
for (int i=0;i<=a;i++){
z[i].clear();
}
for (auto p:s){
z[p.first].push_back(p.second);
}
for (int i=a-1;i>=0;i--){
for (auto p:pos[i]){
for (auto j:v[W[p]]){
if (j.second<=P[p]){
d.join(j.first,j.second);
}
}
res[p]+=d.cnt;
for (auto j:v[W[p]]){
if (j.second<=P[p]){
d.rollback();
}
}
}
for (auto p:z[i]){
d.join(p,i);
}
}
for (auto p:s1){
s.insert(p);
}
}
for (int i=0;i<c;i++){
res[i]=a-res[i];
}
return res;
}