Submission #1043442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043442		AmirAli_H1	Fountain Parks (IOI21_parks)	C++17	70 / 100	457 ms	91168 KiB

parks

// In the name of Allah

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

typedef		long long				ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;

#define		endl					'\n'
#define		sep						' '
#define		F						first
#define		S						second
#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		pb						push_back
#define		Mp						make_pair

const int maxn = 1e6 + 4;

int n;
vector<pii> adj[maxn]; set<pii> E;
vector<pii> arr, arrx;
int val[maxn], D[maxn];
int mark[maxn], h[maxn];
vector<int> ux, vx, X1, Y1;

int GI(pii x) {
	int j = lower_bound(all(arr), x) - arr.begin();
	if (j < len(arr) && arr[j] == x) return j;
	else return -1;
}

int GIx(pii x) {
	int j = lower_bound(all(arrx), x) - arrx.begin();
	if (j < len(arrx) && arrx[j] == x) return j;
	else return -1;
}

bool ok(int x, int y) {
	int j = GI(Mp(x, y));
	return (j != -1);
}

void addE(int x1, int y1, int x2, int y2) {
	int u = val[GI(Mp(x1, y1))], v = val[GI(Mp(x2, y2))];
	if (u > v) swap(u, v);
	E.insert(Mp(u, v));
	D[u]++; D[v]++;
}

void delE(int x1, int y1, int x2, int y2) {
	int u = val[GI(Mp(x1, y1))], v = val[GI(Mp(x2, y2))];
	if (u > v) swap(u, v);
	E.erase(Mp(u, v));
	D[u]--; D[v]--;
}

void dfs(int v) {
	mark[v] = 1;
	for (auto f : adj[v]) {
		int u = f.F;
		if (!mark[u]) dfs(u);
	}
}

void res_dfs(int v, int i = -1) {
	mark[v] = 1;
	for (auto f : adj[v]) {
		int u = f.F, j = f.S;
		if (!mark[u]) {
			h[u] = h[v] + 1;
			res_dfs(u, j);
			X1[j] = arrx[u].F; Y1[j] = arrx[u].S;
		}
		else if (j != i && h[u] < h[v]) {
			X1[j] = arrx[u].F; Y1[j] = arrx[u].S;
		}
	}
}

bool checkx() {
	for (auto f : E) {
		int u = f.F, v = f.S;
		adj[u].pb(Mp(v, -1)); adj[v].pb(Mp(u, -1));
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		if (!mark[i]) return 0;
	}
	for (int i = 0; i < n; i++) {
		mark[i] = 0; adj[i].clear();
	}
	return 1;
}

int construct_roads(vector<int> X, vector<int> Y) {
	n = len(X);
	for (int i = 0; i < n; i++) arr.pb(Mp(X[i], Y[i]));
	sort(all(arr));
	
	for (int i = 0; i < n; i++) {
		int j = GI(Mp(X[i], Y[i]));
		val[j] = i;
	}
	
	for (int i = 0; i < n; i++) {
		if (ok(X[i], Y[i] + 2)) {
			addE(X[i], Y[i], X[i], Y[i] + 2);
		}
		if (ok(X[i] + 2, Y[i]) && (!ok(X[i], Y[i] - 2) || !ok(X[i] + 2, Y[i] - 2))) {
			addE(X[i], Y[i], X[i] + 2, Y[i]);
		}
	}
	
	for (int i = 0; i < n; i++) {
		if (D[i] == 4) {
			if (ok(X[i] + 2, Y[i] + 2)) {
				delE(X[i], Y[i], X[i] + 2, Y[i]);
				addE(X[i], Y[i] + 2, X[i] + 2, Y[i] + 2);
			}
			else if (ok(X[i] - 2, Y[i] + 2)) {
				delE(X[i], Y[i], X[i] - 2, Y[i]);
				addE(X[i], Y[i] + 2, X[i] - 2, Y[i] + 2);
			}
		}
	}
	if (!checkx()) return 0;
	
	for (auto f : E) {
		int u = f.F, v = f.S; pii f1, f2;
		int x = (X[u] + X[v]) / 2, y = (Y[u] + Y[v]) / 2;
		if (X[u] == X[v]) {
			f1 = Mp(x - 1, y); f2 = Mp(x + 1, y);
		}
		else {
			f1 = Mp(x, y - 1); f2 = Mp(x, y + 1);
		}
		arrx.pb(f1); arrx.pb(f2);
	}
	sort(all(arrx)); arrx.resize(unique(all(arrx)) - arrx.begin());
	
	for (auto f : E) {
		int u = f.F, v = f.S; pii f1, f2;
		int x = (X[u] + X[v]) / 2, y = (Y[u] + Y[v]) / 2;
		if (X[u] == X[v]) {
			f1 = Mp(x - 1, y); f2 = Mp(x + 1, y);
		}
		else {
			f1 = Mp(x, y - 1); f2 = Mp(x, y + 1);
		}
		int u1 = GIx(f1), v1 = GIx(f2);
		adj[u1].pb(Mp(v1, len(ux))); adj[v1].pb(Mp(u1, len(ux)));
		ux.pb(u); vx.pb(v);
	}
	
	X1.resize(len(ux)); Y1.resize(len(ux));
	for (int i = 0; i < len(arrx); i++) {
		if (!mark[i]) res_dfs(i);
	}
	
	build(ux, vx, X1, Y1);
	return 1;
}

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