Submission #772892

#	Time	Username	Problem	Language	Result	Execution time	Memory
772892		numberes	Fountain Parks (IOI21_parks)	C++17	0 / 100	10 ms	19096 KiB

parks

/**
 * @date    2023-07-04 19:59:53
 * RAmen!
 */
#include "parks.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define ll long long
using namespace std;
vector<int> U, V, A, B;
map<int, int> c[200005], used[200005];
pii p[200005];
int n, fa[200005];
// B for horizontal edges; W for vertical edges
int fnd(int x) {
	return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}
void add_edge(int u, int v, int a, int b) {
	U.pb(u - 1); V.pb(v - 1); A.pb(a); B.pb(b); used[a][b] = 1;
}
int construct_roads(vector<int> x, vector<int> y) {
	n = (int)x.size();
	for(int i = 0; i < n; i++) {
		c[x[i]][y[i]] = i + 1; fa[i + 1] = i + 1;
		p[i + 1] = mp(x[i], y[i]);
	}
	sort(p + 1, p + n + 1, [&](pii a, pii b){return mp(a.se, a.fi) < mp(b.se, b.fi);});
	for(int l = 1, r; l <= n; l = r + 1) {
		r = l; while(p[r].se == p[l].se) r++; r--;
		for(int i = l; i <= r; i++) {
			int a = p[i].fi, b = p[i].se;
			if(!c[a].count(b - 2)) continue;
			if(fnd(c[a][b]) == fnd(c[a][b - 2])) continue;
			fa[c[a][b]] = c[a][b - 2];
			if((a + 1) % 4 == (b - 1) % 4) { // W
				add_edge(c[a][b - 2], c[a][b], a + 1, b - 1);
			}
			else if(!used[a - 1][b - 1]){ // B
				add_edge(c[a][b - 2], c[a][b], a - 1, b - 1);
			}
		}
		for(int i = l; i <= r; i++) {
			int a = p[i].fi, b = p[i].se;
			if(!c[a - 2].count(b)) continue;
			if(fnd(c[a][b]) == fnd(c[a - 2][b])) continue;
			fa[c[a][b]] = c[a - 2][b];
			if((a - 1) % 4 != (b + 1) % 4) { // B
				add_edge(c[a - 2][b], c[a][b], a - 1, b + 1);
			}
			else if(!used[a - 1][b - 1]){ // B
				add_edge(c[a - 2][b], c[a][b], a - 1, b - 1);
			}
		}
	}
	build(U, V, A, B);
	return 1;
}
/*
.-.
  |
.-.
|
.-.
*/

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