#include "collapse.h"
#include<bits/stdc++.h>
using namespace std;
struct dsurol{
int par[100100],dep[100100],ans;
stack<pair<int,int>>stk;
dsurol(){memset(par,0,sizeof par);memset(dep,0,sizeof dep);ans=0;}
void init(int n){
ans=n;
}
int abp(int n){
return par[n]?abp(par[n]):n;
}
void merge(int a,int b){
a=abp(++a);
b=abp(++b);
if(a-b){
ans--;
if(dep[a]<dep[b])
swap(a,b);
par[b]=a;
stk.push({b,dep[a]});
dep[a]=max(dep[a],dep[b]+1);
}
}
void rerol(){
auto[a,b]=stk.top();
stk.pop();
dep[par[a]]=b;
par[a]=0;
ans++;
}
void rolbak(int n){
while(stk.size()>n)
rerol();
}
} dsu;
vector<pair<int,int>>whattoad[200100];
void add(int i,int l,int r,int ll,int rr,pair<int,int>K){
if(ll<=l&&r<=rr)
return whattoad[i].push_back(K);
if(ll>r||l>rr) return;
add(i*2,l,l+r>>1,ll,rr,K);
add(i*2+1,l+r+2>>1,r,ll,rr,K);
}
vector<int>ans;
void solve(int i,int l,int r){
int k=dsu.stk.size();
for(auto&[a,b]:whattoad[i])
dsu.merge(a,b);
if(l==r)
ans.push_back(dsu.ans);
else solve(i*2,l,l+r>>1),
solve(i*2+1,l+r+2>>1,r);
dsu.rolbak(k);
}
map<pair<int,int>,int> mp;
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) {
dsu.init(N);
int K=T.size();
int c=P[0];
for(int i=0;i<K;i++){
int t=T[i],x=X[i],y=Y[i];
if(x>y)swap(x,y);
if(x<=c&&y>c)continue;
if(!t){
mp[{X[i],Y[i]}]=i+1;
} else {
add(1,1,K,mp[{X[i],Y[i]}],i-1,{X[i],Y[i]});
mp.erase({X[i],Y[i]});
}
}
for(auto[k,x]:mp)
add(1,1,K,x,K,k);
solve(1,1,K);
vector<int>v;
for(auto i:W)
v.push_back(ans[i-1]);
return v;
}
Compilation message
collapse.cpp: In member function 'void dsurol::rolbak(int)':
collapse.cpp:34:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
34 | while(stk.size()>n)
| ~~~~~~~~~~^~
collapse.cpp: In function 'void add(int, int, int, int, int, std::pair<int, int>)':
collapse.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | add(i*2,l,l+r>>1,ll,rr,K);
| ~^~
collapse.cpp:44:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | add(i*2+1,l+r+2>>1,r,ll,rr,K);
| ~~~^~
collapse.cpp: In function 'void solve(int, int, int)':
collapse.cpp:53:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | else solve(i*2,l,l+r>>1),
| ~^~
collapse.cpp:54:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | solve(i*2+1,l+r+2>>1,r);
| ~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
8408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
8408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
6232 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
