oj.uz

Submission #827175

# Submission time Handle Problem Language Result Execution time Memory
827175 2023-08-16T09:38:13 Z Sohsoh84 Fountain Parks (IOI21_parks) C++17
15 / 100
 721 ms 43412 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pll;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};

namespace answer {
	vector<int> u, v, a, b;
}

vector<pair<pll, int>> edges;

int X[MAXN], Y[MAXN], par[MAXN], n;
map<pll, int> mp;

int find(int v) {
	return par[v] == v ? v : par[v] = find(par[v]);
}

inline bool unite(int u_, int v_) {
	int u = find(u_), v = find(v_);
	if (u == v) return false;

	edges.push_back({{u_, v_}, (int)answer::u.size()});

	answer::u.push_back(u_);
	answer::v.push_back(v_);
	par[u] = v;

	return true;
}

int construct_roads(vector<int> x_, vector<int> y_) {
	n = x_.size();
	for (int i = 0; i < n; i++) {
		X[i] = x_[i];
		Y[i] = y_[i];

		mp[pll(X[i], Y[i])] = i;
		par[i] = i;
	}

	int edg = 0;
	for (int i = 0; i < 4; i++) {
		for (int v = 0; v < n; v++) {
			int ux = X[v] + 2 * DX[i], uy = Y[v] + 2 * DY[i];
			auto it = mp.find(pll(ux, uy));
			if (it == mp.end()) continue;

			int u = it -> second;	
			edg += unite(u, v);
		}
	}

	if (edg < n - 1) return 0;

	sort(all(edges), [] (const pair<pll, int>& a, const pair<pll, int>& b) {
		return min(X[a.X.X], X[a.X.Y]) < min(X[b.X.X], X[b.X.Y]);
	});

	set<pll> st;
	for (int ti = 0; ti < n - 1; ti++) {
		int i = ti;

		if (X[answer::u[i]] == X[answer::v[i]]) {
			int tx = X[answer::u[i]] - 1, ty = (Y[answer::u[i]] + Y[answer::v[i]]) / 2;	
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			tx += 2;
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			return 0;
		} else {
			int ty = Y[answer::u[i]] - 1, tx = (X[answer::u[i]] + X[answer::v[i]]) / 2;	
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			ty += 2;
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			return 0;
		}
	}

	build(answer::u, answer::v, answer::a, answer::b);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 190 ms 21296 KB Output is correct
10 Correct 12 ms 2632 KB Output is correct
11 Correct 64 ms 12304 KB Output is correct
12 Correct 16 ms 3772 KB Output is correct
13 Correct 36 ms 5988 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 195 ms 21480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 190 ms 21296 KB Output is correct
10 Correct 12 ms 2632 KB Output is correct
11 Correct 64 ms 12304 KB Output is correct
12 Correct 16 ms 3772 KB Output is correct
13 Correct 36 ms 5988 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 195 ms 21480 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 721 ms 42404 KB Output is correct
24 Correct 0 ms 304 KB Output is correct
25 Correct 2 ms 568 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 5 ms 828 KB Output is correct
28 Correct 179 ms 17296 KB Output is correct
29 Correct 318 ms 25616 KB Output is correct
30 Correct 438 ms 34072 KB Output is correct
31 Correct 657 ms 42412 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 300 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 304 KB Output is correct
38 Correct 1 ms 300 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 304 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 2 ms 468 KB Output is correct
44 Correct 2 ms 612 KB Output is correct
45 Correct 200 ms 21528 KB Output is correct
46 Correct 443 ms 31300 KB Output is correct
47 Correct 347 ms 31244 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 190 ms 21296 KB Output is correct
10 Correct 12 ms 2632 KB Output is correct
11 Correct 64 ms 12304 KB Output is correct
12 Correct 16 ms 3772 KB Output is correct
13 Correct 36 ms 5988 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 195 ms 21480 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 721 ms 42404 KB Output is correct
24 Correct 0 ms 304 KB Output is correct
25 Correct 2 ms 568 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 5 ms 828 KB Output is correct
28 Correct 179 ms 17296 KB Output is correct
29 Correct 318 ms 25616 KB Output is correct
30 Correct 438 ms 34072 KB Output is correct
31 Correct 657 ms 42412 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 300 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 304 KB Output is correct
38 Correct 1 ms 300 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 304 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 2 ms 468 KB Output is correct
44 Correct 2 ms 612 KB Output is correct
45 Correct 200 ms 21528 KB Output is correct
46 Correct 443 ms 31300 KB Output is correct
47 Correct 347 ms 31244 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
52 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 190 ms 21296 KB Output is correct
10 Correct 12 ms 2632 KB Output is correct
11 Correct 64 ms 12304 KB Output is correct
12 Correct 16 ms 3772 KB Output is correct
13 Correct 36 ms 5988 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 195 ms 21480 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 568 ms 43412 KB Output is correct
21 Correct 590 ms 43200 KB Output is correct
22 Correct 580 ms 43172 KB Output is correct
23 Correct 387 ms 36476 KB Output is correct
24 Correct 298 ms 18636 KB Output is correct
25 Correct 527 ms 23808 KB Output is correct
26 Correct 299 ms 23744 KB Output is correct
27 Correct 572 ms 42320 KB Output is correct
28 Incorrect 357 ms 23812 KB Solution announced impossible, but it is possible.
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 190 ms 21296 KB Output is correct
10 Correct 12 ms 2632 KB Output is correct
11 Correct 64 ms 12304 KB Output is correct
12 Correct 16 ms 3772 KB Output is correct
13 Correct 36 ms 5988 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 195 ms 21480 KB Output is correct
17 Correct 531 ms 42784 KB Output is correct
18 Incorrect 514 ms 32968 KB Solution announced impossible, but it is possible.
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 190 ms 21296 KB Output is correct
10 Correct 12 ms 2632 KB Output is correct
11 Correct 64 ms 12304 KB Output is correct
12 Correct 16 ms 3772 KB Output is correct
13 Correct 36 ms 5988 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 195 ms 21480 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 721 ms 42404 KB Output is correct
24 Correct 0 ms 304 KB Output is correct
25 Correct 2 ms 568 KB Output is correct
26 Correct 2 ms 724 KB Output is correct
27 Correct 5 ms 828 KB Output is correct
28 Correct 179 ms 17296 KB Output is correct
29 Correct 318 ms 25616 KB Output is correct
30 Correct 438 ms 34072 KB Output is correct
31 Correct 657 ms 42412 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 300 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 1 ms 304 KB Output is correct
38 Correct 1 ms 300 KB Output is correct
39 Correct 1 ms 212 KB Output is correct
40 Correct 1 ms 304 KB Output is correct
41 Correct 1 ms 212 KB Output is correct
42 Correct 1 ms 212 KB Output is correct
43 Correct 2 ms 468 KB Output is correct
44 Correct 2 ms 612 KB Output is correct
45 Correct 200 ms 21528 KB Output is correct
46 Correct 443 ms 31300 KB Output is correct
47 Correct 347 ms 31244 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
52 Halted 0 ms 0 KB -