Submission #436161

#	Time	Username	Problem	Language	Result	Execution time	Memory
436161		Calico	분수 공원 (IOI21_parks)	C++17	45 / 100	987 ms	35108 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;

struct DSU {
	vector<int> P, S;
	DSU(int n) {
		P.resize(n+1);
		S.resize(n+1, 1);
		for (int i = 1; i <= n; i++) P[i] = i;
	}
	
	int find(int x) {
		if (x == P[x]) return x;
		return P[x] = find(P[x]);
	}
	
	bool merge(int a, int b) {
		a = find(a); b = find(b);
		if (a == b) return 0;
		if (S[a] < S[b]) swap(a, b);
		
		S[a] += S[b];
		P[b] = a;
		return 1;
	}
	
	int same(int a, int b) {
		return find(a) == find(b);
	}
};

vector<int> dx = {-2, 0, 2, 0};
vector<int> dy = {0, -2, 0, 2};

bool ok(vector<int> X, vector<int> Y, vector<pair<int, int>> edges, vector<int> &u, vector<int> &v, vector<int> &a, vector<int> &b, int pr) {
	set<pair<int, int>> st;
	for (auto [i, j]: edges) {
		if (X[i] == X[j]) {
			// vertical 
			int x = X[i] - 1;
			int y = (Y[i] + Y[j])/2;

			if ((x/2 + y/2) % 2 == pr) {
				x = X[i] + 1;
			}

			if (st.find({x, y}) != st.end()) {
				u.clear(); v.clear(); a.clear(); b.clear();
				return 0;
			}

			u.push_back(i);
			v.push_back(j);
			a.push_back(x);
			b.push_back(y);

			st.insert({x, y});
		} else {
			// horizontal
			int x = (X[i] + X[j])/2;
			int y = Y[i]-1;

			if ((x/2 + y/2) % 2 != pr) {
				y = Y[i] + 1;
			}

			if (st.find({x, y}) != st.end()) {
				u.clear(); v.clear(); a.clear(); b.clear();
				return 0;
			}
			
			u.push_back(i);
			v.push_back(j);
			a.push_back(x);
			b.push_back(y);

			st.insert({x, y});
		}
	}

	return 1;
}

int construct_roads(vector<int> X, vector<int> Y) {
	int n = X.size();

	map<pair<int, int>, int> id;
	for (int i = 0; i < n; i++) {
		id[{X[i], Y[i]}] = i;
	}

	DSU d(n);
	int cc = n;

	vector<pair<int, int>> edges;
	for (int i = 0; i < n; i++) {
		if ((X[i]/2 + Y[i]/2) % 2) continue;
		for (int j = 0; j < 4; j++) {
			int x = X[i] + dx[j];
			int y = Y[i] + dy[j];

			if (id.find({x, y}) != id.end()) {
				int u = id[{x, y}];
				if (!d.same(i, u)) {
					edges.emplace_back(i, u);
					d.merge(i, u);
					cc--;
				}
			}
		}
	}
	if (cc != 1) return 0; 

	vector<int> u, v, a, b;
	if (ok(X, Y, edges, u, v, a, b, 0)) {
		build(u, v, a, b);
		return 1;
	}
	if (ok(X, Y, edges, u, v, a, b, 1)) {
		build(u, v, a, b);
		return 1;
	}

	return 1;
}

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