oj.uz

Submission #377671

# Submission time Handle Problem Language Result Execution time Memory
377671 2021-03-14T16:53:05 Z YJU Collapse (JOI18_collapse) C++14
5 / 100
 15000 ms 24956 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);
	//merge nda to ndb
	++now;--cnt;
	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;++cnt;
	}
}
 
set<pll> Edge,init;
ll n,q,c;
ll ty[N],x[N],y[N],w[N],p[N],ans[N];
vector<pll> oper[N];
vector<ll> query[N],Q[N];
 
void solve(){
	//reset
	now=cnt=0;
	REP1(i,n)sz[i]=1,dir[i]=i;
	
	REP(i,q){Q[w[i]].pb(i);}
	for(ll start=0;start<c;start+=K){
		/**/
		Edge.clear();
		init.clear();
		/**/
		for(ll i=0;i<start;i++){
			if(ty[i]==0){
				Edge.insert(mp(x[i],y[i]));
			}else{
				Edge.erase(mp(x[i],y[i]));
			}
		}
		for(ll i=start;i<min(c,start+K);i++){
			if(ty[i]==1&&Edge.find(mp(x[i],y[i]))!=Edge.end()){
				Edge.erase(mp(x[i],y[i]));
				init.insert(mp(x[i],y[i]));
			}
			for(ll j:Q[i]){
				query[p[j]].pb(j);
			}
			/**/Q[i].clear();/**/
		}
		for(auto i:Edge){
			oper[i.Y].pb(mp(i.X,i.Y));
		}
		REP1(i,n){
			/*new node*/++cnt;/**/
			for(pll j:oper[i]){
				Union(j.X,j.Y);
			}
			for(ll j:query[i]){
				/**/ll pos=now;/**/
				set<pll> tmp=init;
				for(ll ii=start;ii<w[j]+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<=i){
						Union(ii.X,ii.Y);
					}
				}
				ans[j]+=cnt;
				/**/restore(pos);/**/
			}
			/**/
			oper[i].clear();
			query[i].clear();
			/**/
		}
		restore(0);
		cnt=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];
	}
}
 
void out(){
	REP(i,c)assert(x[i]<y[i]),assert(x[i]<=n&&x[i]>=1),assert(y[i]<=n&&y[i]>=1);
	//REP(i,c)cout<<ty[i]<<" "<<x[i]<<" "<<y[i]<<"\n";
	//REP(i,q)cout<<p[i]<<" "<<w[i]<<"\n";
}
 
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]);
	}
	REP(i,q){p[i]=_p[i]+1;w[i]=_w[i];}
	out();
	solve();
	rev();
	out();
	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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7916 KB Output is correct
2 Correct 9 ms 7660 KB Output is correct
3 Correct 16 ms 7788 KB Output is correct
4 Correct 21 ms 7788 KB Output is correct
5 Correct 103 ms 8044 KB Output is correct
6 Correct 177 ms 8300 KB Output is correct
7 Correct 8 ms 7916 KB Output is correct
8 Correct 11 ms 7916 KB Output is correct
9 Correct 106 ms 8172 KB Output is correct
10 Correct 198 ms 8428 KB Output is correct
11 Correct 195 ms 8556 KB Output is correct
12 Correct 192 ms 8556 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11752 KB Output is correct
2 Correct 73 ms 12388 KB Output is correct
3 Correct 5366 ms 17488 KB Output is correct
4 Correct 309 ms 12916 KB Output is correct
5 Correct 6844 ms 19308 KB Output is correct
6 Correct 2698 ms 12952 KB Output is correct
7 Execution timed out 15033 ms 24956 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11752 KB Output is correct
2 Correct 73 ms 11752 KB Output is correct
3 Correct 152 ms 12076 KB Output is correct
4 Correct 306 ms 12140 KB Output is correct
5 Correct 2340 ms 11892 KB Output is correct
6 Correct 3064 ms 12804 KB Output is correct
7 Correct 10339 ms 21532 KB Output is correct
8 Execution timed out 15034 ms 24332 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 7916 KB Output is correct
2 Correct 9 ms 7660 KB Output is correct
3 Correct 16 ms 7788 KB Output is correct
4 Correct 21 ms 7788 KB Output is correct
5 Correct 103 ms 8044 KB Output is correct
6 Correct 177 ms 8300 KB Output is correct
7 Correct 8 ms 7916 KB Output is correct
8 Correct 11 ms 7916 KB Output is correct
9 Correct 106 ms 8172 KB Output is correct
10 Correct 198 ms 8428 KB Output is correct
11 Correct 195 ms 8556 KB Output is correct
12 Correct 192 ms 8556 KB Output is correct
13 Correct 46 ms 11752 KB Output is correct
14 Correct 73 ms 12388 KB Output is correct
15 Correct 5366 ms 17488 KB Output is correct
16 Correct 309 ms 12916 KB Output is correct
17 Correct 6844 ms 19308 KB Output is correct
18 Correct 2698 ms 12952 KB Output is correct
19 Execution timed out 15033 ms 24956 KB Time limit exceeded
20 Halted 0 ms 0 KB -