oj.uz

Submission #377676

# Submission time Handle Problem Language Result Execution time Memory
377676 2021-03-14T17:22:24 Z YJU Collapse (JOI18_collapse) C++14
30 / 100
 7348 ms 14956 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll N=1e5+5;
const ll K=sqrt(N);
const ll MOD2=998244353;
const ld pi=acos(-1);
#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 sz[N],dir[N],now,stk[N][2],cnt;
 
ll find(ll id){
	while(id!=dir[id])id=dir[id];
	return id;
}
 
void Union(ll nda,ll ndb){
	nda=find(nda);ndb=find(ndb);
	if(nda==ndb)return ;
	if(sz[nda]>sz[ndb])swap(nda,ndb);
	++now;
	stk[now][0]=nda;stk[now][1]=ndb;
	sz[ndb]+=sz[nda];
	dir[nda]=ndb;
}
 
void restore(ll T){
	while(now>T){
		ll nda=stk[now][0],ndb=stk[now][1];
		sz[ndb]-=sz[nda];
		dir[nda]=nda;
		--now;
	}
}
 
set<pll> Edge,init;
ll n,q,c;
ll ty[N],x[N],y[N],w[N],p[N],ans[N];
vector<pll> oper,query;
vector<ll> Q[N];
map<pll,ll> mm;

ll se1[N],se2[N],num[N];
 
void solve(){
	//reset
	now=cnt=0;
	REP1(i,n)sz[i]=1,dir[i]=i;
	
	for(ll start=0;start<c;start+=K){
		/**/
		memset(se1,0,sizeof(se1));
		init.clear();
		oper.clear();
		query.clear();
		/**/
		for(ll i=0;i<start;i++){
			if(ty[i]==0){
				se1[num[i]]=1;
				//Edge.insert(mp(x[i],y[i]));
			}else{
				se1[num[i]]=0;
			}
		}
		for(ll i=start;i<min(c,start+K);i++){
			if(ty[i]==1&&se1[num[i]]==1){
				se1[num[i]]=0;
				init.insert(mp(x[i],y[i]));
			}
			for(ll j:Q[i]){
				query.pb(mp(p[j],j));
			}
		}
		REP(i,c){
			if(se1[i]){
				se1[i]=0;
				oper.pb(mp(y[i],x[i]));
			}
		}
		sort(oper.begin(),oper.end());
		sort(query.begin(),query.end());
		for(ll i=0,j=0;i<SZ(query);i++){
			while(j<SZ(oper)&&oper[j].X<=query[i].X)Union(oper[j].X,oper[j].Y),++j;
			ll pos=now,qid=query[i].Y;
			set<pll> tmp=init;
			for(ll ii=start;ii<w[qid]+1;ii++){
				if(ty[ii]==1)tmp.erase(mp(x[ii],y[ii]));
				else tmp.insert(mp(x[ii],y[ii]));
			}
			for(pll ii:tmp){
				if(ii.Y<=query[i].X)Union(ii.X,ii.Y);
			}
			ans[qid]+=query[i].X-now;
			restore(pos);
		}
		restore(0);
	}
}
 
void rev(){
	REP(i,c){
		ll xx=x[i],yy=y[i];
		x[i]=n+1-yy;
		y[i]=n+1-xx;
	}
	REP(i,q){
		p[i]=n-p[i];
	}
}
 
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);
	REP(i,c){
		ty[i]=_ty[i];x[i]=_x[i]+1;y[i]=_y[i]+1;
		if(x[i]>y[i])swap(x[i],y[i]);
		if(mm.find(mp(x[i],y[i]))==mm.end()){
			num[i]=i;
		}else{
			num[i]=mm[mp(x[i],y[i])];
		}
	}
	REP(i,q){p[i]=_p[i]+1;w[i]=_w[i];}
	REP(i,q)Q[w[i]].pb(i);
	solve();
	rev();
	solve();
	
	vector<ll> ret;
	REP(i,q)ret.pb(ans[i]);
	return ret;
}
/*
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	vector<ll> T={0,0,0,0,0,0,1,0};
	vector<ll> TX={0,0,1,2,4,4,4,4};
	vector<ll> TY={1,3,2,4,0,3,3,3};
	vector<ll> W={7};
	vector<ll> P={3};
	vector<ll> ans=simulateCollapse(5,T,TX,TY,W,P);
	for(auto i:ans)cout<<i<<"\n";
	return 0;
}
 
//*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3692 KB Output is correct
2 Correct 6 ms 3436 KB Output is correct
3 Correct 14 ms 3436 KB Output is correct
4 Correct 20 ms 3436 KB Output is correct
5 Incorrect 86 ms 3564 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7908 KB Output is correct
2 Correct 82 ms 8032 KB Output is correct
3 Incorrect 3087 ms 14096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7908 KB Output is correct
2 Correct 90 ms 7992 KB Output is correct
3 Correct 165 ms 8180 KB Output is correct
4 Correct 326 ms 8288 KB Output is correct
5 Correct 2539 ms 7808 KB Output is correct
6 Correct 3208 ms 7508 KB Output is correct
7 Correct 5019 ms 12000 KB Output is correct
8 Correct 6975 ms 13748 KB Output is correct
9 Correct 67 ms 8676 KB Output is correct
10 Correct 2993 ms 8184 KB Output is correct
11 Correct 7141 ms 14840 KB Output is correct
12 Correct 7342 ms 14920 KB Output is correct
13 Correct 7235 ms 14700 KB Output is correct
14 Correct 7348 ms 14956 KB Output is correct
15 Correct 7137 ms 14688 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3692 KB Output is correct
2 Correct 6 ms 3436 KB Output is correct
3 Correct 14 ms 3436 KB Output is correct
4 Correct 20 ms 3436 KB Output is correct
5 Incorrect 86 ms 3564 KB Output isn't correct
6 Halted 0 ms 0 KB -