| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 369626 | YJU | Collapse (JOI18_collapse) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=4e5+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
ll n,q,c,dir[N];
set<pll> ms;
ll f(ll id){
return (id==dir[id]?id:dir[id]=f(dir[id]));
}
vector<ll> simulateCollapse(ll _N,vector<ll> ty,vector<ll> x,vector<ll> y,vector<ll> w,vector<ll> p){
n=_N;q=SZ(w);c=SZ(ty);
vector<ll> ret;
REP(i,c){
++x[i];++y[i];
if(x[i]>y[i])swap(x[i],y[i]);
}
REP(i,q)++p[i];
REP(i,q){
ms.clear();
REP(j,w[i]+1){
if(ty[j]==0){
ms.insert(mp(x[j],y[j]));
}else{
ms.erase(mp(x[j],y[j]));
}
}
ll cnt=n;
REP1(j,n)dir[j]=j;
for(auto j:ms){
if(p[i]<j.X||p[i]>=j.Y){
if(f(j.X)==f(j.Y))continue;
--cnt;
dir[f(j.X)]=f(j.Y);
}
}
ret.pb(cnt);
}
return ret;
}
/*
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
vector<ll> T={0,0,0,0};
vector<ll> TX={0,1,2,4};
vector<ll> TY={1,3,4,0};
vector<ll> W={3};
vector<ll> P={1};
vector<ll> ans=simulateCollapse(5,T,TX,TY,W,P);
for(auto i:ans)cout<<i<<"\n";
return 0;
}
*/