Submission #1242901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242901		AMnu	Fountain Parks (IOI21_parks)	C++20	100 / 100	294 ms	41072 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;

const int MAXN = 2e5+5;

int N, P[MAXN], X, Y, A, B, i, j;
vector <int> u, v, a, b;
set <pii> C;
map <pii,int> D;

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

void join(int x,int y) {
	x = find(x);
	y = find(y);
	P[x] = y;
}

void add() {
	if (!C.count({A,B})) {
		C.insert({A,B});
		u.push_back(i);
		v.push_back(j);
		a.push_back(A);
		b.push_back(B);
		join(i,j);
	}
}

int construct_roads(vector<int> x,vector<int> y) {
	N = x.size();
	for (i=0;i<N;i++) {
		D[{x[i],y[i]}] = i;
		P[i] = i;
	}
	for (auto f : D) {
		X = f.fi.fi;
		Y = f.fi.se;
		i = f.se;
		if (D.count({X,Y+2})) {
			A = X + 1 - ((X^Y)&2);
			B = Y + 1;
			j = D[{X,Y+2}];
			add();
		}
		if (D.count({X+2,Y})) {
			A = X + 1;
			B = Y - 1 + ((X^Y)&2);
			j = D[{X+2,Y}];
			add();
		}
	}
	for (i=1;i<N;i++) {
		if (find(i) != find(0)) {
			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