oj.uz

Submission #377675

# Submission time Handle Problem Language Result Execution time Memory
377675 2021-03-14T17:18:06 Z YJU Collapse (JOI18_collapse) C++14
30 / 100
 7571 ms 17376 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 emplace_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;
}
 
inline 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> init;
ll n,q,c;
ll ty[N],x[N],y[N],w[N],p[N],ans[N],num[N],in[N];
vector<pll> oper,query;
vector<ll> Q[N];
 
void solve(){
	//reset
	now=cnt=0;
	REP1(i,n)sz[i]=1,dir[i]=i;
	
	for(ll start=0;start<c;start+=K){
		/**/
		init.clear();
		oper.clear();
		query.clear();
		/**/
		for(ll i=0;i<start;i++){
			if(ty[i]==0){
				in[num[i]]=1;
			}else{
				in[num[i]]=0;
			}
		}
		for(ll i=start;i<min(c,start+K);i++){
			if(ty[i]==1&&in[num[i]]){
				in[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(in[i])oper.pb(mp(y[i],x[i])),in[i]=0;
		
		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){
	map<pll,ll> Map;
	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]);
		num[i]=(Map.find(mp(x[i],y[i]))==Map.end()?i:Map[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 33 ms 3308 KB Output is correct
2 Correct 6 ms 3052 KB Output is correct
3 Correct 13 ms 3052 KB Output is correct
4 Correct 19 ms 3052 KB Output is correct
5 Incorrect 88 ms 3308 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7524 KB Output is correct
2 Correct 79 ms 7648 KB Output is correct
3 Incorrect 3039 ms 14060 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 48 ms 7524 KB Output is correct
2 Correct 90 ms 7648 KB Output is correct
3 Correct 166 ms 7832 KB Output is correct
4 Correct 327 ms 7904 KB Output is correct
5 Correct 2594 ms 7276 KB Output is correct
6 Correct 3286 ms 7528 KB Output is correct
7 Correct 5113 ms 12312 KB Output is correct
8 Correct 7063 ms 13732 KB Output is correct
9 Correct 67 ms 9060 KB Output is correct
10 Correct 3092 ms 8944 KB Output is correct
11 Correct 7155 ms 17344 KB Output is correct
12 Correct 7526 ms 17376 KB Output is correct
13 Correct 7389 ms 17316 KB Output is correct
14 Correct 7571 ms 17376 KB Output is correct
15 Correct 7339 ms 17192 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3308 KB Output is correct
2 Correct 6 ms 3052 KB Output is correct
3 Correct 13 ms 3052 KB Output is correct
4 Correct 19 ms 3052 KB Output is correct
5 Incorrect 88 ms 3308 KB Output isn't correct
6 Halted 0 ms 0 KB -