oj.uz

Submission #1059659

# Submission time Handle Problem Language Result Execution time Memory
1059659 2024-08-15T06:50:15 Z Gromp15 Fountain Parks (IOI21_parks) C++17
5 / 100
 274 ms 41300 KB 
#include <bits/stdc++.h>
#include "parks.h"
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

struct dsu {
	vector<int> p, size;
	dsu(int n) : p(n), size(n, 1) {
		iota(all(p), 0);
	}
	int get(int v) {
		return v == p[v] ? v : p[v] = get(p[v]);
	}
	bool merge(int a, int b) {
		a = get(a), b = get(b);
		if (a == b) return 0;
		if (size[a] < size[b]) swap(a, b);
		size[a] += size[b], p[b] = a;
		return 1;
	}
};

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = sz(x);
	map<ar<int, 4>, int> mp;
	map<ar<int, 2>, int> idx;
	for (int i = 0; i < n; i++) idx[{x[i], y[i]}] = i;
	vector<int> a(n-1), b(n-1), c(n-1), d(n-1);
	dsu D(n);
	int now = 0;
	vector<ar<int, 3>> ord(n);
	for (int i = 0; i < n; i++) ord[i] = {x[i], y[i], i};
	sort(all(ord));
	set<ar<int, 2>> used;
	for (int i = 0; i < n; i++) {
		int r = i;
		while (r+1 < n && ord[r+1][0] == ord[r][0] && ord[r+1][1] == ord[r][1] + 2) r++;
		for (int j = i; j < r; j++) {
			assert(D.merge(ord[j][2], ord[j+1][2]));
			a[now] = ord[j][2], b[now] = ord[j+1][2];
			if ((j - i) % 2 == 0) {
				c[now] = ord[j][0] - 1, d[now] = ord[j][1] + 1;
			}
			else {
				c[now] = ord[j][0] + 1, d[now] = ord[j][1] + 1;
			}
			//cout << "M " << ord[j][0] << " " << ord[j][1] << " " << ord[j+1][0] << " " << ord[j+1][1] << '\n';
			used.insert({c[now], d[now]});
			now++;
		}
		i = r;
	}
	for (auto [x, y, i] : ord) {
		if (idx.count({x + 2, y})) {
			int pos = idx[{x+2, y}];
			if (D.get(pos) == D.get(i)) continue;
			D.merge(pos, i);
			for (int v : {-1, 1}) if (!used.count({x + 1, y + v})) {
				a[now] = i, b[now] = pos;
				c[now] = x + 1, d[now] = y + v;
				used.insert({x + 1, y + v});
				now++;
				break;
			}
		}
	}
	/*
	map<ar<int, 2>, int> adj;
	for (int i = 0; i < n; i++) {
		if (idx.count({x[i] + 2, y[i]})) {
			mp[{x[i], y[i], x[i] + 2, y[i]}] += 2;
			adj[{x[i] + 1, y[i] + 1}]++;
			adj[{x[i] + 1, y[i] - 1}]++;
		}
		if (idx.count({x[i], y[i] + 2})) {
			mp[{x[i], y[i], x[i], y[i] + 2}] += 2;
			adj[{x[i] + 1, y[i] + 1}]++;
			adj[{x[i] - 1, y[i] + 1}]++;
		}
	}
	set<pair<int, ar<int, 2>>> q;
	for (auto [x, y] : adj) q.insert({y, x});
	set<ar<int, 2>> used;
	while (q.size()) {
		auto [val, p] = *q.begin();
		q.erase(q.begin());
		if (val != adj[p]) {
			if (adj[p]) {
				q.insert({adj[p], p});
				continue;
			}
		}
		ar<int, 4> seg2{p[0] - 1, p[1] - 1, p[0] - 1, p[1] + 1};
		ar<int, 4> seg3{p[0] + 1, p[1] - 1, p[0] + 1, p[1] + 1};
		ar<int, 4> seg4{p[0] - 1, p[1] - 1, p[0] + 1, p[1] - 1};
		ar<int, 4> seg5{p[0] - 1, p[1] + 1, p[0] + 1, p[1] + 1};
		bool F = 0;
		for (int tp = 0; tp <= 4; tp++) {
			for (auto& seg : {seg2, seg3, seg4, seg5}) if (mp.count(seg) && mp[seg] == tp) {
				int i1 = idx[{seg[0], seg[1]}], i2 = idx[{seg[2], seg[3]}];
				ar<int, 2> pt, pt2;
				if (seg[0] != seg[2]) {
					pt = {seg[0] + 1, seg[1] - 1};
					pt2 = {seg[0] + 1, seg[1] + 1};
				}
				else {
					pt = {seg[0] - 1, seg[1] + 1};
					pt2 = {seg[0] + 1, seg[1] + 1};
				}
				for (auto p : {pt, pt2}) adj[p]--;
				if (!F && D.get(i1) != D.get(i2)) {
					F = 1;
					D.merge(i1, i2);
					a[now] = i1, b[now] = i2;
					c[now] = p[0], d[now] = p[1];
					now++;
				}
			}
		}
		if (F) for (auto& seg : {seg2, seg3, seg4, seg5}) if (mp.count(seg)) mp[seg]--;
	}
	*/
	if (D.size[D.get(0)] != n) return 0;
	build(a, b, c, d);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 92 ms 20320 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 39 ms 11044 KB Output is correct
12 Correct 10 ms 3496 KB Output is correct
13 Correct 24 ms 7920 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 90 ms 20436 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 92 ms 20320 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 39 ms 11044 KB Output is correct
12 Correct 10 ms 3496 KB Output is correct
13 Correct 24 ms 7920 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 90 ms 20436 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 227 ms 40428 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 72 ms 16280 KB Output is correct
29 Incorrect 118 ms 24328 KB Pair u[119998]=0 @(2, 107882) and v[119998]=0 @(2, 107882) does not form a valid edge (distance != 2)
30 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 92 ms 20320 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 39 ms 11044 KB Output is correct
12 Correct 10 ms 3496 KB Output is correct
13 Correct 24 ms 7920 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 90 ms 20436 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 227 ms 40428 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 72 ms 16280 KB Output is correct
29 Incorrect 118 ms 24328 KB Pair u[119998]=0 @(2, 107882) and v[119998]=0 @(2, 107882) does not form a valid edge (distance != 2)
30 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 92 ms 20320 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 39 ms 11044 KB Output is correct
12 Correct 10 ms 3496 KB Output is correct
13 Correct 24 ms 7920 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 90 ms 20436 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 238 ms 41300 KB Output is correct
21 Correct 274 ms 40908 KB Output is correct
22 Correct 242 ms 41048 KB Output is correct
23 Correct 200 ms 34640 KB Output is correct
24 Correct 128 ms 24648 KB Output is correct
25 Correct 217 ms 34132 KB Output is correct
26 Correct 165 ms 33876 KB Output is correct
27 Correct 211 ms 40276 KB Output is correct
28 Correct 205 ms 40380 KB Output is correct
29 Correct 246 ms 40364 KB Output is correct
30 Correct 259 ms 40272 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Incorrect 19 ms 3416 KB Pair u[13732]=0 @(185792, 20626) and v[13732]=0 @(185792, 20626) does not form a valid edge (distance != 2)
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 92 ms 20320 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 39 ms 11044 KB Output is correct
12 Correct 10 ms 3496 KB Output is correct
13 Correct 24 ms 7920 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 90 ms 20436 KB Output is correct
17 Correct 237 ms 40640 KB Output is correct
18 Correct 252 ms 40788 KB Output is correct
19 Incorrect 232 ms 41044 KB Pair u[199994]=0 @(47612, 97612) and v[199994]=0 @(47612, 97612) does not form a valid edge (distance != 2)
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 92 ms 20320 KB Output is correct
10 Correct 7 ms 2396 KB Output is correct
11 Correct 39 ms 11044 KB Output is correct
12 Correct 10 ms 3496 KB Output is correct
13 Correct 24 ms 7920 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 90 ms 20436 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 227 ms 40428 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 72 ms 16280 KB Output is correct
29 Incorrect 118 ms 24328 KB Pair u[119998]=0 @(2, 107882) and v[119998]=0 @(2, 107882) does not form a valid edge (distance != 2)
30 Halted 0 ms 0 KB -