Submission #1052836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052836		ReLice	Fountain Parks (IOI21_parks)	C++17	30 / 100	373 ms	56836 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define ll int
#define vll vector<ll>
#define fr first
#define sc second
#define pb push_back
#define sz size()
#define bc back()
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
const int inf=1e9;
ll p[N],siz[N];
map<pair<ll,ll>,bool> vis;
map<pair<ll,ll>,ll> f;
ll anc(ll a){
	return (p[a]==a ? a : p[a]=anc(p[a]));
}
bool uni(ll a,ll b){
	a=anc(a);
	b=anc(b);
	if(a==b)return false;
	if(siz[a]>siz[b])swap(a,b);
	p[a]=b;
	siz[b]+=siz[a];
	return true;
}
int construct_roads(vector<int> x, vector<int> y) {
	vis[{x[0],y[0]}]=1;
	vector<pair<ll,pair<ll,ll>>> ver,hor;
	ll n=x.size();
	ll i;
	for(i=0;i<(int)x.size();i++){
		f[{x[i],y[i]}]=i+1;
	}
	for(i=0;i<n;i++){
		p[i]=i;
		siz[i]=1;
		if(f[{x[i]+2,y[i]+0}]){
			hor.pb({x[i],{i,f[{x[i]+2,y[i]+0}]-1}});
		}if(f[{x[i]+0,y[i]+2}]){
			ver.pb({x[i],{i,f[{x[i]+0,y[i]+2}]-1}});
		}
	}
	sort(all(ver));
	sort(all(hor));
	vll U,V,A,B;
	while(ver.sz || hor.sz){
		ll xx;
		if(ver.sz && hor.sz)xx=max(ver.bc.fr,hor.bc.fr);
		else if(ver.sz) xx=ver.bc.fr;
		else xx=hor.bc.fr;
		while(hor.sz && hor.bc.fr==xx){
			ll a=hor.bc.sc.fr,b=hor.bc.sc.sc;
			hor.pop_back();
			if(anc(a)!=anc(b)){
				if(vis[{x[a]+1,y[a]-1}]==0){
					vis[{x[a]+1,y[a]-1}]=1;
					uni(a,b);
					U.pb(a);
					V.pb(b);
					A.pb(x[a]+1);
					B.pb(y[a]-1);
				}
				else if(vis[{x[a]+1,y[a]+1}]==0){
					vis[{x[a]+1,y[a]+1}]=1;
					uni(a,b);
					U.pb(a);
					V.pb(b);
					A.pb(x[a]+1);
					B.pb(y[a]+1);
				}
			}
		}
		while(ver.sz && ver.bc.fr==xx){
			ll a=ver.bc.sc.fr,b=ver.bc.sc.sc;
			ver.pop_back();
			if(anc(a)!=anc(b)){
				if(vis[{x[a]+1,y[a]+1}]==0){
					vis[{x[a]+1,y[a]+1}]=1;
					uni(a,b);
					U.pb(a);
					V.pb(b);
					A.pb(x[a]+1);
					B.pb(y[a]+1);
				}
				else if(vis[{x[a]-1,y[a]+1}]==0){
					vis[{x[a]-1,y[a]+1}]=1;
					uni(a,b);
					U.pb(a);
					V.pb(b);
					A.pb(x[a]-1);
					B.pb(y[a]+1);
					
				}
			}
		}
	}
	if((int)V.size()!=n-1)return 0;
	
	//~ for(int i=0;i<(int)V.size();i++)cout<<V[i]<<' '<<V[i]<<endl;
	//~ for(auto i : A)cout<<i<<' ';
	//~ cout<<endl;
	//~ for(auto i : B)cout<<i<<' ';
	//~ cout<<endl;
	build(U,V,A,B);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30