Submission #435522

#	Time	Username	Problem	Language	Result	Execution time	Memory
435522		b00n0rp	Fountain Parks (IOI21_parks)	C++17	30 / 100	876 ms	49996 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define SZ(v) (int)v.size()
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second

const int MX = 200005;

int n;
pii a[MX];
set<pair<pii,int> > st;

vector<pii> dir = {{-2,0},{2,0},{0,-2},{0,2}};

vi adj[MX];
int par[MX];

int find(int x){
	if(par[x] == x) return x;
	return par[x] = find(par[x]);
}

signed construct_roads(vector<signed> x, vector<signed> y){
	n = SZ(x);
	REP(i,n){
		a[i] = {x[i],y[i]};
		st.insert({a[i],i});
		par[i] = i;
	}
	vector<pii> edges;
	REP(i,n){
		REP(j,4){
			pii bruh = {x[i]+dir[j].F,y[i]+dir[j].S};
			auto it = st.lower_bound({bruh,0});
			if(it != st.end()){
				if((*it).F == bruh){
					adj[i].pb((*it).S);
					if(i < (*it).S) edges.pb({i,(*it).S});
				}
			}
		}
	}
    vector<signed> u0, v0, a0, b0;
	for(auto i:edges){
		int u = i.F,v = i.S;
		// cout << u << " " << v << "\n";
		if(find(u) == find(v)) continue;
		if(a[u] > a[v]) swap(u,v);
		if(x[u] != x[v]){
			continue;
		}
		else{
			par[find(u)] = find(v);
			u0.pb(u);
			v0.pb(v);
			if(x[u] == 2){
				a0.pb(x[u]-1);
				b0.pb(y[u]+1);
			}
			else if(x[u] == 6){
				a0.pb(x[u]+1);
				b0.pb(y[u]+1);
			}
			else if((x[u]+y[u])%4 == 0){
				a0.pb(x[u]-1);
				b0.pb(y[u]+1);
			}
			else{
				a0.pb(x[u]+1);
				b0.pb(y[u]+1);
			}
		}
	}
	for(auto i:edges){
		int u = i.F,v = i.S;
		// cout << u << " " << v << "\n";
		if(find(u) == find(v)) continue;
		if(a[u] > a[v]) swap(u,v);
		if(x[u] != x[v]){
			par[find(u)] = find(v);
			u0.pb(u);
			v0.pb(v);
			if((x[u]+y[u])%4 == 0){
				a0.pb(x[u]+1);
				b0.pb(y[u]+1);
			}
			else{
				a0.pb(x[u]+1);
				b0.pb(y[u]-1);
			}
		}
		else{
			continue;
		}
	}
	REP(i,n){
		if(find(i) != find(1)) return 0;
	}
    build(u0, v0, a0, b0);
    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