Submission #1052976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052976		ReLice	Fountain Parks (IOI21_parks)	C++17	100 / 100	456 ms	56752 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll int
#define ins insert
#define sz size()
#define vll vector<ll>
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
const int inf=1e9;
map<pair<ll,ll>, ll> f;
vll xx, yy;

ll xd[4] = {2, 0}, yd[4] = {0, 2};
ll bx[2][4] = {{1, -1}, { 1, 1}};
ll by[2][4] = {{1,  1}, {-1, 1}};

set<pair<ll,ll>> vis;
vll v,u,a,b;
ll n,c;
ll p[N], siz[N];
bool ok(ll x,ll y){
	if(x % 2) return (vis.find({x, y}) == vis.end());
	return f[{x,y}];
}

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;
}

void go(ll x, ll y){
	c++;
	for(ll i=0;i<2;i++){
		ll nx = x + xd[i], ny = y + yd[i];
		
		ll p = (x + y) / 2 % 2;
		ll aa = x + bx[p][i], bb = y + by[p][i];
		
		if(!ok(nx, ny) || !ok(aa, bb) || !uni(f[{nx,ny}],f[{x,y}])) continue;
		
		v.pb(f[{x,y}]-1);
		u.pb(f[{nx,ny}]-1);
		a.pb(aa);
		b.pb(bb);
		
		vis.ins({aa, bb});
	}
}
int construct_roads(vector<int> X, vector<int> Y) {
	n=X.size();
	vector<array<int,3>> V;
	
	for(int i=0;i<n;i++){
		f[{X[i], Y[i]}] = i + 1;
		V.pb({X[i] + Y[i], X[i], i + 1});
	}
	
	sort(all(V));
	
	xx.pb(0);
	yy.pb(0);
	for(auto i : X) xx.pb(i);
	for(auto i : Y) yy.pb(i);
	
	for(ll i=1;i<=n;i++){p[i]=i,siz[i]=1;}
	
	for(ll i=0;i<n;i++){
		ll x = xx[V[i][2]];
		ll y = yy[V[i][2]];
		//~ cout<<x<<' '<<y<<endl;
		go(x,y);
	}
	
	//~ for(ll i=0;i<(ll)u.size();i++){
		//~ cout<<X[v[i]]<<' '<<Y[v[i]]<<endl;
		//~ cout<<X[u[i]]<<' '<<Y[u[i]]<<endl;
		//~ cout<<a[i]<<' '<<b[i]<<endl;
		//~ cout<<endl;
	//~ }
	
	if((ll)u.size() != n - 1) return 0;
	
	build(u, v, a, b);
	
	return 1;
}

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