oj.uz

Submission #925414

# Submission time Handle Problem Language Result Execution time Memory
925414 2024-02-11T15:02:02 Z Itamar Fountain Parks (IOI21_parks) C++17
45 / 100
 1141 ms 118988 KB 
using namespace std;
#include <vector>
#include "parks.h"
#include <map>
#define pi pair<int,int>
#define vi vector<int>
const int siz = 2e5 + 2;
map<pi, int> m;
int my[siz];
vi col[siz];
#include <set>
bool con(int a, int b) {
	if (my[a] == my[b])return 0;
	a = my[a], b = my[b];
	if (col[a].size() > col[b].size())swap(a, b);
	for (int x : col[a]) {
		my[x] = b;
		col[b].push_back(x);
	}
	return 1;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = x.size();
	for (int i = 0; i < n; i++) {
		m[{x[i], y[i]}] = i + 1;
	}
	vector<pi> ed1, ed2;
	for (int i = 0; i < n; i++) {
		if (m[{x[i] + 2, y[i]}])ed1.push_back({ i+1,m[{x[i] + 2, y[i]}] });
		if (m[{x[i], y[i] + 2}])ed2.push_back({ i+1,m[{x[i],y[i] + 2}] });
	}
	vector<pi> ed; for (pi p : ed2)ed.push_back(p); for (pi p : ed1)ed.push_back(p);
	vector<pi> ans;
	for (int i = 0; i <= n; i++) {
		my[i] = i; col[i].push_back(i);
	}
	for (pi e : ed) {
		if (con(e.first, e.second))ans.push_back(e);
	}
	if (ans.size()+1 < n )return 0;
	vi ans1(n - 1), ans2(n - 1), ans3(n - 1), ans4(n - 1);

	for (int i = 0; i < n - 1; i++) {
		ans1[i] = ans[i].first - 1; ans2[i] = ans[i].second - 1;
	}
	map<pi, vi> fr;
	vector<vector<pi>> fr2(n - 1);
	for (int i = 0; i < n - 1; i++) {
		if (x[ans[i].first - 1] == x[ans[i].second - 1]) {
			int mid = (y[ans[i].first - 1] + y[ans[i].second - 1]) / 2;
			fr[{x[ans[i].first - 1]-1, mid}].push_back(i);
			fr[{x[ans[i].first - 1]+1, mid}].push_back(i);
			fr2[i].push_back({ x[ans[i].first - 1]-1, mid });
			fr2[i].push_back({ x[ans[i].first - 1]+1, mid });
		}
		else {
			int mid = (x[ans[i].first - 1] + x[ans[i].second - 1]) / 2;
			fr[{mid,y[ans[i].first - 1]+1}].push_back(i);
			fr[{mid,y[ans[i].first - 1]-1}].push_back(i);
			fr2[i].push_back( {mid,y[ans[i].first - 1]-1 });
			fr2[i].push_back( {mid,y[ans[i].first - 1]+1} );
		}
	}
	vector<pi> deg1;
	for (pair<pi, vi> p : fr)if (p.second.size() == 1)deg1.push_back(p.first);

	while(!deg1.empty()){

		pi poi = deg1.back();
		deg1.pop_back();
			while (fr[poi].size() == 1) {
				int i = fr[poi][0];
				fr[poi].pop_back();
				if (fr2[i].back() != poi)swap(fr2[i][0], fr2[i][1]);
				fr2[i].pop_back();
				ans3[i] = poi.first, ans4[i] = poi.second;
				if (fr2[i].size() == 1) {
					poi = fr2[i][0];
					if (fr[poi].size()) {
						if (fr[poi].back() != i)swap(fr[poi][0], fr[poi][1]);
						fr[poi].pop_back();
						if (fr[poi].size() == 1)deg1.push_back(poi);
					}
				}
			}
	}
	for (pair<pi, vi> p : fr) {
		pi poi = p.first;
		if (p.second.size() == 2)fr[poi].pop_back();
		while (fr[poi].size() == 1) {
			int i = fr[poi][0];
			fr[poi].pop_back();
			if (fr2[i].back() != poi)swap(fr2[i][0], fr2[i][1]);
			fr2[i].pop_back();
			ans3[i] = poi.first, ans4[i] = poi.second;
			if (fr2[i].size() == 1) {
				poi = fr2[i][0];
				if (fr[poi].size()) {
					if (fr[poi].back() != i)swap(fr[poi][0], fr[poi][1]);
					fr[poi].pop_back();
				}
			}
		}
	}
	build(ans1, ans2, ans3, ans4);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:42:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |  if (ans.size()+1 < n )return 0;
      |      ~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 483 ms 61376 KB Output is correct
10 Correct 25 ms 10712 KB Output is correct
11 Correct 153 ms 34244 KB Output is correct
12 Correct 39 ms 13528 KB Output is correct
13 Correct 32 ms 14680 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 460 ms 61200 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 483 ms 61376 KB Output is correct
10 Correct 25 ms 10712 KB Output is correct
11 Correct 153 ms 34244 KB Output is correct
12 Correct 39 ms 13528 KB Output is correct
13 Correct 32 ms 14680 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 460 ms 61200 KB Output is correct
17 Correct 1 ms 5468 KB Output is correct
18 Correct 2 ms 5468 KB Output is correct
19 Incorrect 1 ms 5468 KB a[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 483 ms 61376 KB Output is correct
10 Correct 25 ms 10712 KB Output is correct
11 Correct 153 ms 34244 KB Output is correct
12 Correct 39 ms 13528 KB Output is correct
13 Correct 32 ms 14680 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 460 ms 61200 KB Output is correct
17 Correct 1 ms 5468 KB Output is correct
18 Correct 2 ms 5468 KB Output is correct
19 Incorrect 1 ms 5468 KB a[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 483 ms 61376 KB Output is correct
10 Correct 25 ms 10712 KB Output is correct
11 Correct 153 ms 34244 KB Output is correct
12 Correct 39 ms 13528 KB Output is correct
13 Correct 32 ms 14680 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 460 ms 61200 KB Output is correct
17 Correct 1 ms 5468 KB Output is correct
18 Correct 1 ms 5468 KB Output is correct
19 Correct 1 ms 5468 KB Output is correct
20 Correct 813 ms 88156 KB Output is correct
21 Correct 926 ms 94996 KB Output is correct
22 Correct 851 ms 87820 KB Output is correct
23 Correct 802 ms 102284 KB Output is correct
24 Correct 393 ms 52816 KB Output is correct
25 Correct 363 ms 48816 KB Output is correct
26 Correct 359 ms 48732 KB Output is correct
27 Correct 1082 ms 117944 KB Output is correct
28 Correct 1080 ms 117484 KB Output is correct
29 Correct 979 ms 115448 KB Output is correct
30 Correct 971 ms 115508 KB Output is correct
31 Correct 2 ms 5464 KB Output is correct
32 Correct 38 ms 11856 KB Output is correct
33 Correct 133 ms 28780 KB Output is correct
34 Correct 852 ms 94500 KB Output is correct
35 Correct 10 ms 7516 KB Output is correct
36 Correct 57 ms 15152 KB Output is correct
37 Correct 133 ms 24880 KB Output is correct
38 Correct 269 ms 39988 KB Output is correct
39 Correct 417 ms 52752 KB Output is correct
40 Correct 600 ms 66068 KB Output is correct
41 Correct 759 ms 78648 KB Output is correct
42 Correct 996 ms 91832 KB Output is correct
43 Correct 2 ms 5468 KB Output is correct
44 Correct 1 ms 5468 KB Output is correct
45 Correct 1 ms 5468 KB Output is correct
46 Correct 1 ms 5468 KB Output is correct
47 Correct 2 ms 5464 KB Output is correct
48 Correct 1 ms 5468 KB Output is correct
49 Correct 2 ms 5468 KB Output is correct
50 Correct 2 ms 5468 KB Output is correct
51 Correct 1 ms 5512 KB Output is correct
52 Correct 2 ms 5468 KB Output is correct
53 Correct 1 ms 5468 KB Output is correct
54 Correct 3 ms 5724 KB Output is correct
55 Correct 3 ms 5980 KB Output is correct
56 Correct 427 ms 52732 KB Output is correct
57 Correct 669 ms 74560 KB Output is correct
58 Correct 661 ms 74572 KB Output is correct
59 Correct 1 ms 5464 KB Output is correct
60 Correct 1 ms 5468 KB Output is correct
61 Correct 1 ms 5468 KB Output is correct
62 Correct 1098 ms 118988 KB Output is correct
63 Correct 1109 ms 118176 KB Output is correct
64 Correct 1141 ms 117412 KB Output is correct
65 Correct 4 ms 6488 KB Output is correct
66 Correct 8 ms 6964 KB Output is correct
67 Correct 381 ms 51400 KB Output is correct
68 Correct 682 ms 74936 KB Output is correct
69 Correct 1050 ms 98172 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 483 ms 61376 KB Output is correct
10 Correct 25 ms 10712 KB Output is correct
11 Correct 153 ms 34244 KB Output is correct
12 Correct 39 ms 13528 KB Output is correct
13 Correct 32 ms 14680 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 460 ms 61200 KB Output is correct
17 Correct 944 ms 117816 KB Output is correct
18 Correct 1002 ms 117808 KB Output is correct
19 Correct 858 ms 91624 KB Output is correct
20 Correct 962 ms 91676 KB Output is correct
21 Correct 889 ms 92416 KB Output is correct
22 Correct 1 ms 5464 KB Output is correct
23 Correct 101 ms 19076 KB Output is correct
24 Correct 20 ms 9056 KB Output is correct
25 Correct 103 ms 18988 KB Output is correct
26 Correct 179 ms 27832 KB Output is correct
27 Correct 394 ms 48416 KB Output is correct
28 Correct 561 ms 59096 KB Output is correct
29 Correct 684 ms 70400 KB Output is correct
30 Correct 777 ms 81052 KB Output is correct
31 Correct 1020 ms 91708 KB Output is correct
32 Correct 1029 ms 102588 KB Output is correct
33 Correct 1070 ms 118968 KB Output is correct
34 Correct 5 ms 6488 KB Output is correct
35 Correct 9 ms 7260 KB Output is correct
36 Correct 417 ms 52152 KB Output is correct
37 Correct 756 ms 76680 KB Output is correct
38 Correct 1112 ms 99984 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct
3 Correct 1 ms 5468 KB Output is correct
4 Correct 1 ms 5468 KB Output is correct
5 Correct 2 ms 5464 KB Output is correct
6 Correct 2 ms 5468 KB Output is correct
7 Correct 1 ms 5468 KB Output is correct
8 Correct 2 ms 5468 KB Output is correct
9 Correct 483 ms 61376 KB Output is correct
10 Correct 25 ms 10712 KB Output is correct
11 Correct 153 ms 34244 KB Output is correct
12 Correct 39 ms 13528 KB Output is correct
13 Correct 32 ms 14680 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 3 ms 5724 KB Output is correct
16 Correct 460 ms 61200 KB Output is correct
17 Correct 1 ms 5468 KB Output is correct
18 Correct 2 ms 5468 KB Output is correct
19 Incorrect 1 ms 5468 KB a[4] = 0 is not an odd integer
20 Halted 0 ms 0 KB -