Submission #1052915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052915		ReLice	Fountain Parks (IOI21_parks)	C++17	55 / 100	461 ms	96124 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, 2, 0, 0}, yd[4] = {0, 0, -2, 2};
ll bx[2][4] = {{-1, 1,  1, -1}, {-1,  1, -1,  1}};
ll by[2][4] = {{-1, 1, -1,  1}, { 1, -1, -1,  1}};

set<pair<ll,ll>> vis;
vll v,u,a,b;
ll n,c;
bool ok(ll x,ll y){
	bool free = (vis.find({x, y}) == vis.end());
	if(x % 2) return free;
	return free && f[{x,y}];
}
void dfs(ll x, ll y){
	vis.ins({x, y});
	c++;
	for(ll i=3;i>=0;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)) continue;
		
		v.pb(f[{x,y}]-1);
		u.pb(f[{nx,ny}]-1);
		a.pb(aa);
		b.pb(bb);
		
		vis.ins({aa, bb});
		
		dfs(nx, ny);
	}
}
int construct_roads(vector<int> X, vector<int> Y) {
	n=X.size();
	vector<pair<ll,ll>> V;
	
	for(int i=0;i<(int)X.size();i++){
		f[{X[i], Y[i]}] = i + 1;
		V.pb({X[i],Y[i]});
	}
	
	sort(all(V));
	
	xx.pb(0);
	yy.pb(0);
	for(auto i : X) xx.pb(i);
	for(auto i : Y) yy.pb(i);
	
	dfs(V[0].fr, V[0].sc);
	
	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: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30