oj.uz

Submission #377663

# Submission time Handle Problem Language Result Execution time Memory
377663 2021-03-14T16:25:33 Z YJU Collapse (JOI18_collapse) C++14
0 / 100
 15000 ms 17900 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
	cnt=now=0;
	REP1(i,n)sz[i]=1,dir[i]=i;
	REP(i,N)Q[i].clear(),oper[i].clear(),query[i].clear();
	
	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);
			}
		}
		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<min(min(c,start+K),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);/**/
			}
		}
	}
}

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(){
	return ;
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 7916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11752 KB Output is correct
2 Correct 82 ms 12388 KB Output is correct
3 Execution timed out 15045 ms 17900 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 11752 KB Output is correct
2 Correct 75 ms 11880 KB Output is correct
3 Correct 149 ms 12076 KB Output is correct
4 Correct 301 ms 12268 KB Output is correct
5 Incorrect 2312 ms 11900 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 7916 KB Output isn't correct
2 Halted 0 ms 0 KB -