oj.uz

Submission #377678

# Submission time Handle Problem Language Result Execution time Memory
377678 2021-03-14T17:23:46 Z YJU Collapse (JOI18_collapse) C++14
100 / 100
 7530 ms 24576 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]=mm[mp(x[i],y[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
5.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 14 ms 3052 KB Output is correct
4 Correct 19 ms 3052 KB Output is correct
5 Correct 92 ms 3180 KB Output is correct
6 Correct 166 ms 3564 KB Output is correct
7 Correct 5 ms 3052 KB Output is correct
8 Correct 8 ms 3052 KB Output is correct
9 Correct 97 ms 3436 KB Output is correct
10 Correct 181 ms 3436 KB Output is correct
11 Correct 176 ms 3692 KB Output is correct
12 Correct 177 ms 3692 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7524 KB Output is correct
2 Correct 86 ms 7648 KB Output is correct
3 Correct 2325 ms 13312 KB Output is correct
4 Correct 329 ms 8032 KB Output is correct
5 Correct 3250 ms 13824 KB Output is correct
6 Correct 3242 ms 7532 KB Output is correct
7 Correct 6643 ms 20844 KB Output is correct
8 Correct 3266 ms 19004 KB Output is correct
9 Correct 53 ms 9060 KB Output is correct
10 Correct 110 ms 9184 KB Output is correct
11 Correct 2936 ms 9156 KB Output is correct
12 Correct 3141 ms 20164 KB Output is correct
13 Correct 5330 ms 21820 KB Output is correct
14 Correct 6510 ms 24576 KB Output is correct
15 Correct 6498 ms 24504 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7484 KB Output is correct
2 Correct 91 ms 7648 KB Output is correct
3 Correct 196 ms 7876 KB Output is correct
4 Correct 336 ms 8032 KB Output is correct
5 Correct 2543 ms 7472 KB Output is correct
6 Correct 3238 ms 7596 KB Output is correct
7 Correct 5091 ms 16944 KB Output is correct
8 Correct 7009 ms 19936 KB Output is correct
9 Correct 66 ms 8292 KB Output is correct
10 Correct 3079 ms 8116 KB Output is correct
11 Correct 7220 ms 21112 KB Output is correct
12 Correct 7476 ms 21324 KB Output is correct
13 Correct 7366 ms 21048 KB Output is correct
14 Correct 7504 ms 21204 KB Output is correct
15 Correct 7277 ms 21160 KB Output is correct

Subtask #4
35.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 14 ms 3052 KB Output is correct
4 Correct 19 ms 3052 KB Output is correct
5 Correct 92 ms 3180 KB Output is correct
6 Correct 166 ms 3564 KB Output is correct
7 Correct 5 ms 3052 KB Output is correct
8 Correct 8 ms 3052 KB Output is correct
9 Correct 97 ms 3436 KB Output is correct
10 Correct 181 ms 3436 KB Output is correct
11 Correct 176 ms 3692 KB Output is correct
12 Correct 177 ms 3692 KB Output is correct
13 Correct 51 ms 7524 KB Output is correct
14 Correct 86 ms 7648 KB Output is correct
15 Correct 2325 ms 13312 KB Output is correct
16 Correct 329 ms 8032 KB Output is correct
17 Correct 3250 ms 13824 KB Output is correct
18 Correct 3242 ms 7532 KB Output is correct
19 Correct 6643 ms 20844 KB Output is correct
20 Correct 3266 ms 19004 KB Output is correct
21 Correct 53 ms 9060 KB Output is correct
22 Correct 110 ms 9184 KB Output is correct
23 Correct 2936 ms 9156 KB Output is correct
24 Correct 3141 ms 20164 KB Output is correct
25 Correct 5330 ms 21820 KB Output is correct
26 Correct 6510 ms 24576 KB Output is correct
27 Correct 6498 ms 24504 KB Output is correct
28 Correct 49 ms 7484 KB Output is correct
29 Correct 91 ms 7648 KB Output is correct
30 Correct 196 ms 7876 KB Output is correct
31 Correct 336 ms 8032 KB Output is correct
32 Correct 2543 ms 7472 KB Output is correct
33 Correct 3238 ms 7596 KB Output is correct
34 Correct 5091 ms 16944 KB Output is correct
35 Correct 7009 ms 19936 KB Output is correct
36 Correct 66 ms 8292 KB Output is correct
37 Correct 3079 ms 8116 KB Output is correct
38 Correct 7220 ms 21112 KB Output is correct
39 Correct 7476 ms 21324 KB Output is correct
40 Correct 7366 ms 21048 KB Output is correct
41 Correct 7504 ms 21204 KB Output is correct
42 Correct 7277 ms 21160 KB Output is correct
43 Correct 2810 ms 17392 KB Output is correct
44 Correct 6782 ms 21740 KB Output is correct
45 Correct 3197 ms 17904 KB Output is correct
46 Correct 7035 ms 22304 KB Output is correct
47 Correct 70 ms 9208 KB Output is correct
48 Correct 115 ms 9184 KB Output is correct
49 Correct 2940 ms 9244 KB Output is correct
50 Correct 3807 ms 10624 KB Output is correct
51 Correct 3536 ms 18856 KB Output is correct
52 Correct 4888 ms 19960 KB Output is correct
53 Correct 4929 ms 19444 KB Output is correct
54 Correct 5516 ms 20976 KB Output is correct
55 Correct 5581 ms 20760 KB Output is correct
56 Correct 6229 ms 21700 KB Output is correct
57 Correct 6856 ms 22892 KB Output is correct
58 Correct 6871 ms 22928 KB Output is correct
59 Correct 7154 ms 23620 KB Output is correct
60 Correct 7530 ms 23724 KB Output is correct