Submission #628115

#	Time	Username	Problem	Language	Result	Execution time	Memory
628115		MilosMilutinovic	Fountain Parks (IOI21_parks)	C++17	100 / 100	441 ms	32568 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int n, x[200005], y[200005];
PII ord[200005];
int rt[200005];
int root(int x)
{
	return rt[x] == x ? x : rt[x] = root(rt[x]);
}
map<PII, int> idx;
vector<int> u, v, a, b;
void add(int i, int j)
{
	u.push_back(i);
	v.push_back(j);
	assert(root(i) != root(j));
	rt[root(i)] = root(j);
	if(x[i] == x[j]) {
		if((x[i] + y[i]) % 4 == 2) a.push_back(x[i] - 1);
		else a.push_back(x[i] + 1);
		b.push_back((y[i] + y[j]) / 2);
	} else {
		a.push_back((x[i] + x[j]) / 2);
		if((x[i] + y[i]) % 4 == 2) b.push_back(y[i] + 1);
		else b.push_back(y[i] - 1);
	}
}
int construct_roads(vector<int> X, vector<int> Y)
{
	n = (int) X.size();
	rep(i, n) {
		x[i] = X[i];
		y[i] = Y[i];
		rt[i] = i;
		idx[{x[i], y[i]}] = i;
	}

    rep(i, n) ord[i] = MP(x[i] + y[i], i);
	sort(ord, ord + n);
	reverse(ord, ord + n);
	rep(id, n) {
		int i = ord[id].second;
		int id0 = (idx.count(MP(x[i] + 2, y[i])) ? idx[MP(x[i] + 2, y[i])] : -1);
		int id1 = (idx.count(MP(x[i], y[i] + 2)) ? idx[MP(x[i], y[i] + 2)] : -1);
		if(id0 == -1 && id1 == -1) continue;
		if(id0 != -1 && id1 == -1) add(i, id0);
		if(id0 == -1 && id1 != -1) add(i, id1);
		if(id0 != -1 && id1 != -1) {
			if(root(id0) != root(id1)) {
				add(i, id0); add(i, id1);
			} else {
				if(ord[id].first % 4 == 2) add(i, id1);
				else add(i, id0);
			}
		}
	}

	if((int) 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