oj.uz

Submission #773471

# Submission time Handle Problem Language Result Execution time Memory
773471 2023-07-05T05:50:18 Z SanguineChameleon Fountain Parks (IOI21_parks) C++17
55 / 100
 833 ms 102528 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
vector<int> adj[maxn * 3];
bool flag[maxn * 3];
map<pair<int, int>, int> even_id;
map<pair<int, int>, int> odd_id;
vector<pair<int, int>> odds;
vector<pair<int, int>> roads;
int node_cnt;
int road_cnt;
vector<int> path;

int get_even_id(int x, int y) {
	auto it = even_id.find(make_pair(x, y));
	if (it == even_id.end()) {
		return -1;
	}
	else {
		return it->second;
	}
}

int get_odd_id(int x, int y) {
	auto it = odd_id.find(make_pair(x, y));
	if (it != odd_id.end()) {
		return it->second;
	}
	else {
		odds.emplace_back(x, y);
		return odd_id[make_pair(x, y)] = node_cnt++;
	}
}

void add_edge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void dfs(int u) {
	flag[u] = true;
	path.push_back(u);
	for (auto v: adj[u]) {
		if (!flag[v]) {
			dfs(v);
		}
	}
}

int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	for (int i = 0; i < n; i++) {
		even_id[make_pair(x[i], y[i])] = i;
	}
	for (int u = 0; u < n; u++) {
		int v = get_even_id(x[u] + 2, y[u]);
		if (v != -1) {
			roads.emplace_back(u, v);
			add_edge(u, v);
		}
		v = get_even_id(x[u], y[u] + 2);
		if (v != -1) {
			roads.emplace_back(u, v);
			add_edge(u, v);
		}
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		if (!flag[i]) {
			return 0;
		}
	}
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}
	bool sub2 = true;
	for (int i = 0; i < n; i++) {
		sub2 &= x[i] <= 4;
	}
	road_cnt = roads.size();
	node_cnt = road_cnt;
	if (sub2) {
		vector<int> _u, _v, a, b;
		for (int i = 0; i < road_cnt; i++) {
			int u = roads[i].first;
			int v = roads[i].second;
			_u.push_back(u);
			_v.push_back(v);
			if (y[u] == y[v]) {
				a.push_back(x[u] + 1);
				b.push_back(y[u] + 1);
			}
			else if (x[u] == 2) {
				a.push_back(x[u] - 1);
				b.push_back(y[u] + 1);
			}
			else {
				a.push_back(x[u] + 1);
				b.push_back(y[u] + 1);
			}
		}
		build(_u, _v, a, b);
		return 1;
	}
	for (int i = 0; i < road_cnt; i++) {
		int u = roads[i].first;
		int v = roads[i].second;
		if (y[u] == y[v]) {
			add_edge(i, get_odd_id(x[u] + 1, y[u] - 1));
			add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
		}
		else {
			add_edge(i, get_odd_id(x[u] - 1, y[u] + 1));
			add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
		}
	}
	vector<int> u, v, a, b;
	for (int i = 0; i < node_cnt; i++) {
		flag[i] = false;
	}
	for (int iter = 0; iter < 2; iter++) {
		for (int i = road_cnt; i < node_cnt; i++) {
			if (!flag[i] && (iter == 1 || (int)adj[i].size() == 1)) {
				path.clear();
				dfs(i);
				for (int j = 0; j + 1 < (int)path.size(); j += 2) {
					u.push_back(roads[path[j + 1]].first);
					v.push_back(roads[path[j + 1]].second);
					a.push_back(odds[path[j] - road_cnt].first);
					b.push_back(odds[path[j] - road_cnt].second);
				}
			}
		}
	}
	build(u, v, a, b);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14352 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 6 ms 14292 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 123 ms 37460 KB Output is correct
10 Correct 14 ms 16816 KB Output is correct
11 Correct 51 ms 26900 KB Output is correct
12 Correct 21 ms 17932 KB Output is correct
13 Correct 30 ms 21300 KB Output is correct
14 Correct 7 ms 14496 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 131 ms 35520 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14352 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 6 ms 14292 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 123 ms 37460 KB Output is correct
10 Correct 14 ms 16816 KB Output is correct
11 Correct 51 ms 26900 KB Output is correct
12 Correct 21 ms 17932 KB Output is correct
13 Correct 30 ms 21300 KB Output is correct
14 Correct 7 ms 14496 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 131 ms 35520 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 8 ms 14404 KB Output is correct
19 Correct 8 ms 14332 KB Output is correct
20 Correct 7 ms 14308 KB Output is correct
21 Correct 8 ms 14292 KB Output is correct
22 Correct 8 ms 14292 KB Output is correct
23 Correct 433 ms 68832 KB Output is correct
24 Correct 7 ms 14292 KB Output is correct
25 Correct 8 ms 14664 KB Output is correct
26 Correct 9 ms 14800 KB Output is correct
27 Correct 10 ms 14932 KB Output is correct
28 Correct 123 ms 35636 KB Output is correct
29 Correct 238 ms 47052 KB Output is correct
30 Correct 324 ms 57700 KB Output is correct
31 Correct 454 ms 68204 KB Output is correct
32 Correct 8 ms 14292 KB Output is correct
33 Correct 9 ms 14292 KB Output is correct
34 Correct 8 ms 14420 KB Output is correct
35 Correct 7 ms 14404 KB Output is correct
36 Correct 7 ms 14400 KB Output is correct
37 Correct 7 ms 14400 KB Output is correct
38 Correct 7 ms 14292 KB Output is correct
39 Correct 7 ms 14292 KB Output is correct
40 Correct 7 ms 14292 KB Output is correct
41 Correct 7 ms 14400 KB Output is correct
42 Correct 7 ms 14308 KB Output is correct
43 Correct 8 ms 14672 KB Output is correct
44 Correct 8 ms 14696 KB Output is correct
45 Correct 148 ms 36912 KB Output is correct
46 Correct 222 ms 48248 KB Output is correct
47 Correct 227 ms 47884 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14352 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 6 ms 14292 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 123 ms 37460 KB Output is correct
10 Correct 14 ms 16816 KB Output is correct
11 Correct 51 ms 26900 KB Output is correct
12 Correct 21 ms 17932 KB Output is correct
13 Correct 30 ms 21300 KB Output is correct
14 Correct 7 ms 14496 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 131 ms 35520 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 8 ms 14404 KB Output is correct
19 Correct 8 ms 14332 KB Output is correct
20 Correct 7 ms 14308 KB Output is correct
21 Correct 8 ms 14292 KB Output is correct
22 Correct 8 ms 14292 KB Output is correct
23 Correct 433 ms 68832 KB Output is correct
24 Correct 7 ms 14292 KB Output is correct
25 Correct 8 ms 14664 KB Output is correct
26 Correct 9 ms 14800 KB Output is correct
27 Correct 10 ms 14932 KB Output is correct
28 Correct 123 ms 35636 KB Output is correct
29 Correct 238 ms 47052 KB Output is correct
30 Correct 324 ms 57700 KB Output is correct
31 Correct 454 ms 68204 KB Output is correct
32 Correct 8 ms 14292 KB Output is correct
33 Correct 9 ms 14292 KB Output is correct
34 Correct 8 ms 14420 KB Output is correct
35 Correct 7 ms 14404 KB Output is correct
36 Correct 7 ms 14400 KB Output is correct
37 Correct 7 ms 14400 KB Output is correct
38 Correct 7 ms 14292 KB Output is correct
39 Correct 7 ms 14292 KB Output is correct
40 Correct 7 ms 14292 KB Output is correct
41 Correct 7 ms 14400 KB Output is correct
42 Correct 7 ms 14308 KB Output is correct
43 Correct 8 ms 14672 KB Output is correct
44 Correct 8 ms 14696 KB Output is correct
45 Correct 148 ms 36912 KB Output is correct
46 Correct 222 ms 48248 KB Output is correct
47 Correct 227 ms 47884 KB Output is correct
48 Incorrect 7 ms 14292 KB Tree (a[2], b[2]) = (5, 1) is not adjacent to edge between u[2]=1 @(4, 2) and v[2]=3 @(4, 4)
49 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14352 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 6 ms 14292 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 123 ms 37460 KB Output is correct
10 Correct 14 ms 16816 KB Output is correct
11 Correct 51 ms 26900 KB Output is correct
12 Correct 21 ms 17932 KB Output is correct
13 Correct 30 ms 21300 KB Output is correct
14 Correct 7 ms 14496 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 131 ms 35520 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 6 ms 14292 KB Output is correct
19 Correct 7 ms 14292 KB Output is correct
20 Correct 596 ms 93136 KB Output is correct
21 Correct 715 ms 82420 KB Output is correct
22 Correct 645 ms 82336 KB Output is correct
23 Correct 510 ms 86864 KB Output is correct
24 Correct 203 ms 30048 KB Output is correct
25 Correct 298 ms 37996 KB Output is correct
26 Correct 268 ms 38040 KB Output is correct
27 Correct 694 ms 92872 KB Output is correct
28 Correct 651 ms 92844 KB Output is correct
29 Correct 683 ms 92832 KB Output is correct
30 Correct 714 ms 92752 KB Output is correct
31 Correct 6 ms 14292 KB Output is correct
32 Correct 34 ms 19292 KB Output is correct
33 Correct 86 ms 22184 KB Output is correct
34 Correct 674 ms 93288 KB Output is correct
35 Correct 14 ms 15572 KB Output is correct
36 Correct 51 ms 20356 KB Output is correct
37 Correct 114 ms 26336 KB Output is correct
38 Correct 217 ms 39716 KB Output is correct
39 Correct 301 ms 48564 KB Output is correct
40 Correct 412 ms 59048 KB Output is correct
41 Correct 592 ms 68152 KB Output is correct
42 Correct 706 ms 77088 KB Output is correct
43 Correct 7 ms 14292 KB Output is correct
44 Correct 7 ms 14292 KB Output is correct
45 Correct 7 ms 14292 KB Output is correct
46 Correct 7 ms 14396 KB Output is correct
47 Correct 8 ms 14292 KB Output is correct
48 Correct 7 ms 14292 KB Output is correct
49 Correct 7 ms 14292 KB Output is correct
50 Correct 6 ms 14292 KB Output is correct
51 Correct 7 ms 14364 KB Output is correct
52 Correct 6 ms 14292 KB Output is correct
53 Correct 7 ms 14292 KB Output is correct
54 Correct 7 ms 14548 KB Output is correct
55 Correct 8 ms 14676 KB Output is correct
56 Correct 132 ms 36064 KB Output is correct
57 Correct 220 ms 47020 KB Output is correct
58 Correct 222 ms 46676 KB Output is correct
59 Correct 6 ms 14292 KB Output is correct
60 Correct 7 ms 14372 KB Output is correct
61 Correct 6 ms 14292 KB Output is correct
62 Correct 608 ms 99436 KB Output is correct
63 Correct 625 ms 99568 KB Output is correct
64 Correct 627 ms 100236 KB Output is correct
65 Correct 12 ms 14804 KB Output is correct
66 Correct 12 ms 15340 KB Output is correct
67 Correct 257 ms 48136 KB Output is correct
68 Correct 554 ms 67084 KB Output is correct
69 Correct 680 ms 82304 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14352 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 6 ms 14292 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 123 ms 37460 KB Output is correct
10 Correct 14 ms 16816 KB Output is correct
11 Correct 51 ms 26900 KB Output is correct
12 Correct 21 ms 17932 KB Output is correct
13 Correct 30 ms 21300 KB Output is correct
14 Correct 7 ms 14496 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 131 ms 35520 KB Output is correct
17 Correct 647 ms 102528 KB Output is correct
18 Correct 652 ms 98912 KB Output is correct
19 Correct 622 ms 93080 KB Output is correct
20 Correct 820 ms 86836 KB Output is correct
21 Correct 622 ms 83932 KB Output is correct
22 Correct 7 ms 14292 KB Output is correct
23 Correct 72 ms 25664 KB Output is correct
24 Correct 24 ms 16952 KB Output is correct
25 Correct 77 ms 22896 KB Output is correct
26 Correct 152 ms 29460 KB Output is correct
27 Correct 300 ms 50188 KB Output is correct
28 Correct 414 ms 60332 KB Output is correct
29 Correct 551 ms 69432 KB Output is correct
30 Correct 693 ms 77612 KB Output is correct
31 Correct 796 ms 85936 KB Output is correct
32 Correct 833 ms 94584 KB Output is correct
33 Correct 692 ms 102152 KB Output is correct
34 Correct 11 ms 15132 KB Output is correct
35 Correct 12 ms 15572 KB Output is correct
36 Correct 294 ms 50600 KB Output is correct
37 Correct 528 ms 70164 KB Output is correct
38 Correct 770 ms 88164 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14292 KB Output is correct
2 Correct 6 ms 14292 KB Output is correct
3 Correct 6 ms 14292 KB Output is correct
4 Correct 6 ms 14352 KB Output is correct
5 Correct 7 ms 14292 KB Output is correct
6 Correct 6 ms 14292 KB Output is correct
7 Correct 7 ms 14368 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 123 ms 37460 KB Output is correct
10 Correct 14 ms 16816 KB Output is correct
11 Correct 51 ms 26900 KB Output is correct
12 Correct 21 ms 17932 KB Output is correct
13 Correct 30 ms 21300 KB Output is correct
14 Correct 7 ms 14496 KB Output is correct
15 Correct 8 ms 14548 KB Output is correct
16 Correct 131 ms 35520 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 8 ms 14404 KB Output is correct
19 Correct 8 ms 14332 KB Output is correct
20 Correct 7 ms 14308 KB Output is correct
21 Correct 8 ms 14292 KB Output is correct
22 Correct 8 ms 14292 KB Output is correct
23 Correct 433 ms 68832 KB Output is correct
24 Correct 7 ms 14292 KB Output is correct
25 Correct 8 ms 14664 KB Output is correct
26 Correct 9 ms 14800 KB Output is correct
27 Correct 10 ms 14932 KB Output is correct
28 Correct 123 ms 35636 KB Output is correct
29 Correct 238 ms 47052 KB Output is correct
30 Correct 324 ms 57700 KB Output is correct
31 Correct 454 ms 68204 KB Output is correct
32 Correct 8 ms 14292 KB Output is correct
33 Correct 9 ms 14292 KB Output is correct
34 Correct 8 ms 14420 KB Output is correct
35 Correct 7 ms 14404 KB Output is correct
36 Correct 7 ms 14400 KB Output is correct
37 Correct 7 ms 14400 KB Output is correct
38 Correct 7 ms 14292 KB Output is correct
39 Correct 7 ms 14292 KB Output is correct
40 Correct 7 ms 14292 KB Output is correct
41 Correct 7 ms 14400 KB Output is correct
42 Correct 7 ms 14308 KB Output is correct
43 Correct 8 ms 14672 KB Output is correct
44 Correct 8 ms 14696 KB Output is correct
45 Correct 148 ms 36912 KB Output is correct
46 Correct 222 ms 48248 KB Output is correct
47 Correct 227 ms 47884 KB Output is correct
48 Incorrect 7 ms 14292 KB Tree (a[2], b[2]) = (5, 1) is not adjacent to edge between u[2]=1 @(4, 2) and v[2]=3 @(4, 4)
49 Halted 0 ms 0 KB -