#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
using pl=pair<ll,ll>;
typedef vector<pl> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define dame(a) {out(a);return 0;}
#define rsort(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> void outp(T p){printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvp(T v){for(auto p:v)printf("(%d,%d)",p.fi,p.se);cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
#include "collapse.h"
class UF{
vi par,sz;
public:
ll cnt;
vp memo;
UF(ll n){
par=vi(n,-1);sz=vi(n,1);cnt=n;
}
ll root(ll i){if(par[i]==-1)return i;return root(par[i]);}
void merge(ll a,ll b,bool flag){
a=root(a);b=root(b);
if(a==b)return;
if(sz[a]>sz[b])swap(a,b);
if(flag){memo.pb(a,par[a]);memo.pb(b,sz[b]);}
par[a]=b;sz[b]+=sz[a];cnt--;
}
void rollback(){
while(!memo.empty()){
sz[memo.back().fi]=memo.back().se;memo.pop_back();
par[memo.back().fi]=memo.back().se;memo.pop_back();
cnt++;
}
}
};
vector<int> simulateCollapse(int n,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
ll C=T.size(),Q=W.size(),B=300;
rep(i,C)if(X[i]>Y[i])swap(X[i],Y[i]);
vp srtedge(C);
vi edgeid(C);
rep(i,C)srtedge[i]=pl(X[i],Y[i]);
sort(all(srtedge));
rep(i,C)edgeid[i]=lb(srtedge,pl(X[i],Y[i]));
vvp query(C/B+1);
rep(i,Q){
query[W[i]/B].pb(P[i],i);
}
vector<int> ans(Q);
rep(i,query.size())sort(all(query[i]));
rep(i,query.size()){
vb special(C,false);REP(j,i*B,min(C,(i+1)*B))special[edgeid[j]]=true;
vi con(C);rep(j,i*B)con[edgeid[j]]=1-con[edgeid[j]];
UF uf(n);
vp s;rep(j,i*B)if(con[edgeid[j]]&&!special[edgeid[j]])s.pb(Y[j],X[j]);
sort(all(s));
ll w=0;
vb used(C,false);
for(auto x:query[i]){
while(w!=s.size()&&s[w].fi<=x.fi){
uf.merge(s[w].fi,s[w].se,0);
w++;
}
for(int j=W[x.se];j>=i*B;j--)if(Y[j]<=x.fi&&!used[edgeid[j]]){
if(!T[j])uf.merge(X[j],Y[j],1);
used[edgeid[j]]=true;
}
REP(j,W[x.se]+1,min(C,(i+1)*B))if(Y[j]<=x.fi&&!used[edgeid[j]]&&con[edgeid[j]]){
used[edgeid[j]]=true;
uf.merge(X[j],Y[j],1);
}
ans[x.se]+=uf.cnt-(n-P[x.se]-1);
REP(j,W[x.se],min(C,(i+1)*B))used[edgeid[j]]=false;
uf.rollback();
}
}
// outv(ans);
rep(i,query.size())reverse(all(query[i]));
rep(i,query.size()){
vb special(C,false);REP(j,i*B,min(C,(i+1)*B))special[edgeid[j]]=true;
vi con(C);rep(j,i*B)con[edgeid[j]]=1-con[edgeid[j]];
UF uf(n);
vp s;rep(j,i*B)if(con[edgeid[j]]&&!special[edgeid[j]])s.pb(X[j],Y[j]);
rsort(s);
vb used(C,false);
ll w=0;
for(auto x:query[i]){
while(w!=s.size()&&s[w].fi>x.fi){
uf.merge(s[w].fi,s[w].se,0);
w++;
}
for(int j=W[x.se];j>=i*B;j--)if(X[j]>x.fi&&!used[edgeid[j]]){
if(!T[j])uf.merge(X[j],Y[j],1);
used[edgeid[j]]=true;
}
REP(j,W[x.se]+1,min(C,(i+1)*B))if(X[j]>x.fi&&!used[edgeid[j]]&&con[edgeid[j]]){
used[edgeid[j]]=true;
uf.merge(X[j],Y[j],1);
}
ans[x.se]+=uf.cnt-P[x.se]-1;
uf.rollback();
}
}
return ans;
}
Compilation message
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:77:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | while(w!=s.size()&&s[w].fi<=x.fi){
| ~^~~~~~~~~~
collapse.cpp:105:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | while(w!=s.size()&&s[w].fi>x.fi){
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
876 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
4064 KB |
Output is correct |
| 2 |
Incorrect |
46 ms |
4064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
4064 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
4064 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
876 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
