oj.uz

Submission #1043638

# Submission time Handle Problem Language Result Execution time Memory
1043638 2024-08-04T12:44:36 Z 42kangaroo Fountain Parks (IOI21_parks) C++17
55 / 100
 3500 ms 96952 KB 
#include "parks.h"
#include "bits/stdc++.h"

using namespace std;

struct Po {
	int x, y, f;
};

bool operator<(const Po& l, const Po& r) {
	return tie(l.x, l.y) < tie(r.x, r.y);
}

bool operator==(const Po& l, const Po& r) {
	return tie(l.x, l.y) == tie(r.x, r.y);
}

struct Ed {
	int s, t;
	Po be;
};

int find(int x, vector<int>& p) {
	if (p[x] == x) return x;
	return p[x] = find(p[x], p);
}

void unite(int a, int b, vector<int>& p) {
	a = find(a, p);
	b = find(b, p);
	p[a] = b;
}

using g_t = map<Po, set<Po>>;

int construct_roads(std::vector<int> x, std::vector<int> y) {
	vector<int> p(x.size());
	set<Po> par;
	for (int i = 0; i < x.size(); ++i) {
		p[i] = i;
		par.insert({x[i], y[i], i});
	}
	vector<Ed> eds;
	for (int i = 0; i < x.size(); ++i) {
		if (par.find({x[i], y[i] + 2}) != par.end() && find(par.find({x[i], y[i] + 2})->f, p) != find(i, p)) {
			eds.push_back({par.find({x[i], y[i] + 2})->f, i});
			unite(par.find({x[i], y[i] + 2})->f, i, p);
		}
		if (par.find({x[i] + 2, y[i]}) != par.end() && find(par.find({x[i] + 2, y[i]})->f, p) != find(i, p)) {
			eds.push_back({par.find({x[i] + 2, y[i]})->f, i});
			unite(par.find({x[i] + 2, y[i]})->f, i, p);
		}
	}
	if (eds.size() + 1 < x.size()) return 0;
	g_t g;
	for (int j = 0; j < eds.size(); ++j) {
		if (x[eds[j].s] == x[eds[j].t]) {
			g[{x[eds[j].s] + 1, (y[eds[j].s] + y[eds[j].t])/2}].insert({x[eds[j].s] - 1,(y[eds[j].s] + y[eds[j].t])/2, j});
			g[{x[eds[j].s] - 1, (y[eds[j].s] + y[eds[j].t])/2}].insert({x[eds[j].s] + 1,(y[eds[j].s] + y[eds[j].t])/2, j});
		} else {
			g[{(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] + 1}].insert({(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] - 1, j});
			g[{(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] - 1}].insert({(x[eds[j].s] + x[eds[j].t] )/ 2, y[eds[j].s] + 1, j});
		}
	}
	queue<Po> ne;
	for (auto [st, en]: g) {
		if (en.size() == 1) ne.push(st);
	}
	while (!ne.empty()) {
		auto to = ne.front();
		ne.pop();
		if (g[to].empty()) {
			g.erase(to);
			continue;
		}
		eds[g[to].begin()->f].be = to;
		g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
		if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
		g.erase(to);
	}
	while (!g.empty()) {
		if (g.begin()->second.empty()) g.erase(g.begin());
		else {
			assert(g.begin()->second.size() == 2);
			auto to = g.begin()->first;
			eds[g[to].begin()->f].be = to;
			g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
			if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
			while (!ne.empty()) {
				to = ne.front();
				ne.pop();
				if (g[to].empty()) {
					g.erase(to);
					continue;
				}
				eds[g[to].begin()->f].be = to;
				g[{g[to].begin()->x, g[to].begin()->y}].erase({to.x, to.y, g[to].begin()->f});
				if (g[{g[to].begin()->x, g[to].begin()->y}].size() == 1) ne.push({g[to].begin()->x, g[to].begin()->y});
				g.erase(to);
			}
		}
	}
	vector<int> u(eds.size()), v(eds.size()), a(eds.size()), b(eds.size());
	for (int i = 0; i < eds.size(); ++i) {
		tie(u[i], v[i], a[i], b[i]) = tie(eds[i].s, eds[i].t, eds[i].be.x, eds[i].be.y);
	}
	build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for (int i = 0; i < x.size(); ++i) {
      |                  ~~^~~~~~~~~~
parks.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < x.size(); ++i) {
      |                  ~~^~~~~~~~~~
parks.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ed>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int j = 0; j < eds.size(); ++j) {
      |                  ~~^~~~~~~~~~~~
parks.cpp:104:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Ed>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for (int i = 0; i < eds.size(); ++i) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 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 0 ms 348 KB Output is correct
9 Correct 234 ms 48168 KB Output is correct
10 Correct 14 ms 5076 KB Output is correct
11 Correct 94 ms 26216 KB Output is correct
12 Correct 21 ms 7576 KB Output is correct
13 Correct 27 ms 5712 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 246 ms 48064 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 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 0 ms 348 KB Output is correct
9 Correct 234 ms 48168 KB Output is correct
10 Correct 14 ms 5076 KB Output is correct
11 Correct 94 ms 26216 KB Output is correct
12 Correct 21 ms 7576 KB Output is correct
13 Correct 27 ms 5712 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 246 ms 48064 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 652 ms 76560 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 3 ms 940 KB Output is correct
28 Correct 179 ms 30656 KB Output is correct
29 Correct 334 ms 46016 KB Output is correct
30 Correct 445 ms 61624 KB Output is correct
31 Correct 613 ms 76216 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 436 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 268 ms 40020 KB Output is correct
46 Correct 391 ms 58188 KB Output is correct
47 Correct 422 ms 59280 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 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 0 ms 348 KB Output is correct
9 Correct 234 ms 48168 KB Output is correct
10 Correct 14 ms 5076 KB Output is correct
11 Correct 94 ms 26216 KB Output is correct
12 Correct 21 ms 7576 KB Output is correct
13 Correct 27 ms 5712 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 246 ms 48064 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 652 ms 76560 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 3 ms 940 KB Output is correct
28 Correct 179 ms 30656 KB Output is correct
29 Correct 334 ms 46016 KB Output is correct
30 Correct 445 ms 61624 KB Output is correct
31 Correct 613 ms 76216 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 436 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 268 ms 40020 KB Output is correct
46 Correct 391 ms 58188 KB Output is correct
47 Correct 422 ms 59280 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Execution timed out 3599 ms 73088 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 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 0 ms 348 KB Output is correct
9 Correct 234 ms 48168 KB Output is correct
10 Correct 14 ms 5076 KB Output is correct
11 Correct 94 ms 26216 KB Output is correct
12 Correct 21 ms 7576 KB Output is correct
13 Correct 27 ms 5712 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 246 ms 48064 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 404 KB Output is correct
20 Correct 486 ms 70248 KB Output is correct
21 Correct 563 ms 70060 KB Output is correct
22 Correct 508 ms 69816 KB Output is correct
23 Correct 487 ms 82112 KB Output is correct
24 Correct 152 ms 18512 KB Output is correct
25 Correct 217 ms 25116 KB Output is correct
26 Correct 225 ms 23748 KB Output is correct
27 Correct 653 ms 96668 KB Output is correct
28 Correct 620 ms 96204 KB Output is correct
29 Correct 547 ms 96952 KB Output is correct
30 Correct 577 ms 95928 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 32 ms 5784 KB Output is correct
33 Correct 64 ms 9816 KB Output is correct
34 Correct 500 ms 70332 KB Output is correct
35 Correct 7 ms 1688 KB Output is correct
36 Correct 44 ms 6336 KB Output is correct
37 Correct 95 ms 12488 KB Output is correct
38 Correct 190 ms 30400 KB Output is correct
39 Correct 313 ms 41404 KB Output is correct
40 Correct 403 ms 54200 KB Output is correct
41 Correct 547 ms 64700 KB Output is correct
42 Correct 668 ms 75296 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 432 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 2 ms 604 KB Output is correct
55 Correct 2 ms 600 KB Output is correct
56 Correct 240 ms 39876 KB Output is correct
57 Correct 404 ms 59168 KB Output is correct
58 Correct 408 ms 58676 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 617 ms 96088 KB Output is correct
63 Correct 625 ms 95928 KB Output is correct
64 Correct 598 ms 96440 KB Output is correct
65 Correct 3 ms 860 KB Output is correct
66 Correct 5 ms 1372 KB Output is correct
67 Correct 251 ms 39104 KB Output is correct
68 Correct 451 ms 60108 KB Output is correct
69 Correct 672 ms 79548 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 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 0 ms 348 KB Output is correct
9 Correct 234 ms 48168 KB Output is correct
10 Correct 14 ms 5076 KB Output is correct
11 Correct 94 ms 26216 KB Output is correct
12 Correct 21 ms 7576 KB Output is correct
13 Correct 27 ms 5712 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 246 ms 48064 KB Output is correct
17 Correct 562 ms 96392 KB Output is correct
18 Correct 548 ms 96696 KB Output is correct
19 Correct 528 ms 70840 KB Output is correct
20 Correct 649 ms 73696 KB Output is correct
21 Correct 523 ms 76732 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 65 ms 12476 KB Output is correct
24 Correct 15 ms 2952 KB Output is correct
25 Correct 67 ms 9576 KB Output is correct
26 Correct 122 ms 15912 KB Output is correct
27 Correct 277 ms 38340 KB Output is correct
28 Correct 370 ms 47916 KB Output is correct
29 Correct 483 ms 58552 KB Output is correct
30 Correct 544 ms 68540 KB Output is correct
31 Correct 654 ms 76568 KB Output is correct
32 Correct 582 ms 81864 KB Output is correct
33 Correct 571 ms 96444 KB Output is correct
34 Correct 4 ms 1112 KB Output is correct
35 Correct 6 ms 1592 KB Output is correct
36 Correct 268 ms 39444 KB Output is correct
37 Correct 456 ms 59716 KB Output is correct
38 Correct 653 ms 79908 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 344 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 0 ms 348 KB Output is correct
9 Correct 234 ms 48168 KB Output is correct
10 Correct 14 ms 5076 KB Output is correct
11 Correct 94 ms 26216 KB Output is correct
12 Correct 21 ms 7576 KB Output is correct
13 Correct 27 ms 5712 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 246 ms 48064 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 652 ms 76560 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 3 ms 940 KB Output is correct
28 Correct 179 ms 30656 KB Output is correct
29 Correct 334 ms 46016 KB Output is correct
30 Correct 445 ms 61624 KB Output is correct
31 Correct 613 ms 76216 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 344 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 348 KB Output is correct
39 Correct 0 ms 436 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 2 ms 604 KB Output is correct
45 Correct 268 ms 40020 KB Output is correct
46 Correct 391 ms 58188 KB Output is correct
47 Correct 422 ms 59280 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Execution timed out 3599 ms 73088 KB Time limit exceeded
56 Halted 0 ms 0 KB -