oj.uz

Submission #827153

# Submission time Handle Problem Language Result Execution time Memory
827153 2023-08-16T09:20:22 Z ymm Fountain Parks (IOI21_parks) C++17
55 / 100
 3119 ms 76012 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 200'010;

namespace dsu {
	int par[N];
	void init(int n) { memset(par, -1, sizeof(*par)*n); }
	int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
	bool unite(int v, int u) {
		v = rt(v);
		u = rt(u);
		if (v == u)
			return 0;
		par[u] = v;
		return 1;
	}
}

map<pii,int> pts;
vector<pii> edge;
vector<int> X, Y;
int n;

int get_pnt(int x, int y)
{
	auto it = pts.find(pii(x, y));
	return it == pts.end()? -1: it->second;
}

tuple<int,int,int,int> get_chair(int p1, int p2)
{
	int x1 = X[p1], y1 = Y[p1], x2 = X[p2], y2 = Y[p2];
	if (x1 == x2)
		return {x1-1, (y1+y2)/2, x1+1, (y1+y2)/2};
	else
		return {(x1+x2)/2, y1-1, (x1+x2)/2, y1+1};
}

namespace matching {
	int match[3*N];
	int par[3*N];
	vector<int> A[3*N];
	vector<pii> chairs;

	bool bfs(int s)
	{
		vector<int> q = {s}, q2;
		par[s] = -2;
		int vv;
		Loop (i,0,q.size()) {
			int v = q[i];
			//cerr << "bfs " << v << '\n';
			for (int u : A[v]) {
				if (par[u] != -1)
					continue;
				par[u] = v;
				q2.push_back(u);
				if (match[u] == -1) {
					vv = u;
					goto found;
				}
				int u2 = match[u];
				par[u2] = u;
				q.push_back(u2);
			}
		}
		return 0;
	found:
		while (vv != -2) {
			match[vv] = par[vv];
			match[par[vv]] = vv;
			vv = par[par[vv]];
		}
		for (int x : q2)
			par[x] = -1;
		return 1;
	}

	vector<pii> get_match(vector<pii> e) {
		int m = e.size();
		chairs.clear();
		Loop (i,0,m) {
			auto [p1, p2] = e[i];
			auto [x1, y1, x2, y2] = get_chair(p1, p2);
			chairs.emplace_back(x1, y1);
			chairs.emplace_back(x2, y2);
		}
		sort(chairs.begin(), chairs.end());
		chairs.resize(unique(chairs.begin(), chairs.end()) - chairs.begin());
		//for (auto [x, y] : chairs)
		//	cerr << x << ' ' << y << '\n';
		Loop (i,0,m+chairs.size()) {
			A[i].clear();
			match[i] = -1;
			par[i] = -1;
		}
		Loop (i,0,m) {
			auto [p1, p2] = e[i];
			auto [x1, y1, x2, y2] = get_chair(p1, p2);
			int c1 = lower_bound(chairs.begin(), chairs.end(), pii(x1, y1)) - chairs.begin();
			int c2 = lower_bound(chairs.begin(), chairs.end(), pii(x2, y2)) - chairs.begin();
			A[i].push_back(m+c1);
			A[i].push_back(m+c2);
			A[m+c1].push_back(i);
			A[m+c2].push_back(i);
		}
		Loop (i,0,m) {
			//cerr << "try " << i << '\n';
			if (!bfs(i))
				return {};
			//Loop (i,0,m+chairs.size())
			//	cerr << match[i] << ' ';
			//cerr << '\n';
		}
		//cerr << "all good!\n";
		vector<pii> ans;
		Loop (i,0,m) {
			int c = match[i]-m;
			ans.emplace_back(chairs[c].first, chairs[c].second);
		}
		return ans;
	}
}

void make_edges()
{
	Loop (i,0,n) {
		int x = X[i];
		int y = Y[i];
		if (x%2 == 0)
			continue;
		int p1 = get_pnt(x+2, y);
		int p2 = get_pnt(x, y+2);
		if (p1 != -1)
			edge.push_back({i, p1});
		if (p2 != -1)
			edge.push_back({i, p2});
	}
	Loop (i,0,n) {
		int x = X[i];
		int y = Y[i];
		if (x%2 == 1)
			continue;
		int p1 = get_pnt(x+2, y);
		int p2 = get_pnt(x, y+2);
		if (p1 != -1)
			edge.push_back({i, p1});
		if (p2 != -1)
			edge.push_back({i, p2});
	}
}

int construct_roads(std::vector<int> _X, std::vector<int> _Y) {
	X = _X; Y = _Y;
	n = X.size();
	if (n == 1) {
		build({}, {}, {}, {});
		return 1;
	}
	Loop (i,0,n)
		pts[pii(X[i], Y[i])] = i;
	make_edges();
	//for (auto [x, y] : edge)
	//	cerr << X[x] << ' ' << Y[x] << " - " << X[y] << ' ' << Y[y] << '\n';
	mt19937_64 rd(time(0));
	while (clock() < 3*CLOCKS_PER_SEC) {
		dsu::init(n);
		int cnt = 0;
		vector<pii> e;
		for (auto [x, y] : edge) {
			if (dsu::unite(x, y)) {
				e.emplace_back(x, y);
				++cnt;
			}
		}
		if (cnt != n-1)
			return 0;
		auto chairs = matching::get_match(e);
		//cerr << "found!\n";
		//for (auto [x, y] : chairs)
		//	cerr << x << ' ' << y << '\n';
		if (chairs.empty())
			continue;
		vector<int> ex, ey, cx, cy;
		Loop (i,0,n-1) {
			ex.push_back(e[i].first);
			ey.push_back(e[i].second);
			cx.push_back(chairs[i].first);
			cy.push_back(chairs[i].second);
		}
		build(ex, ey, cx, cy);
		return 1;
	}
	return 0;
}

Compilation message

parks.cpp: In function 'bool matching::bfs(int)':
parks.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
parks.cpp:55:3: note: in expansion of macro 'Loop'
   55 |   Loop (i,0,q.size()) {
      |   ^~~~
parks.cpp: In function 'std::vector<std::pair<int, int> > matching::get_match(std::vector<std::pair<int, int> >)':
parks.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
parks.cpp:97:3: note: in expansion of macro 'Loop'
   97 |   Loop (i,0,m+chairs.size()) {
      |   ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 14304 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14328 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 175 ms 44816 KB Output is correct
10 Correct 20 ms 17520 KB Output is correct
11 Correct 64 ms 30672 KB Output is correct
12 Correct 22 ms 19044 KB Output is correct
13 Correct 26 ms 19468 KB Output is correct
14 Correct 6 ms 14420 KB Output is correct
15 Correct 7 ms 14588 KB Output is correct
16 Correct 171 ms 44832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 14304 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14328 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 175 ms 44816 KB Output is correct
10 Correct 20 ms 17520 KB Output is correct
11 Correct 64 ms 30672 KB Output is correct
12 Correct 22 ms 19044 KB Output is correct
13 Correct 26 ms 19468 KB Output is correct
14 Correct 6 ms 14420 KB Output is correct
15 Correct 7 ms 14588 KB Output is correct
16 Correct 171 ms 44832 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 6 ms 14316 KB Output is correct
19 Correct 6 ms 14292 KB Output is correct
20 Correct 6 ms 14376 KB Output is correct
21 Correct 7 ms 14292 KB Output is correct
22 Correct 6 ms 14292 KB Output is correct
23 Correct 415 ms 71256 KB Output is correct
24 Correct 6 ms 14292 KB Output is correct
25 Correct 9 ms 14672 KB Output is correct
26 Correct 8 ms 14712 KB Output is correct
27 Correct 12 ms 14824 KB Output is correct
28 Correct 145 ms 36732 KB Output is correct
29 Correct 218 ms 48296 KB Output is correct
30 Correct 347 ms 59504 KB Output is correct
31 Correct 410 ms 71340 KB Output is correct
32 Correct 6 ms 14292 KB Output is correct
33 Correct 6 ms 14292 KB Output is correct
34 Correct 7 ms 14292 KB Output is correct
35 Correct 6 ms 14292 KB Output is correct
36 Correct 6 ms 14292 KB Output is correct
37 Correct 6 ms 14364 KB Output is correct
38 Correct 6 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 14296 KB Output is correct
42 Correct 6 ms 14292 KB Output is correct
43 Correct 7 ms 14548 KB Output is correct
44 Correct 8 ms 14680 KB Output is correct
45 Correct 197 ms 42376 KB Output is correct
46 Correct 293 ms 56136 KB Output is correct
47 Correct 313 ms 56076 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 14304 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14328 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 175 ms 44816 KB Output is correct
10 Correct 20 ms 17520 KB Output is correct
11 Correct 64 ms 30672 KB Output is correct
12 Correct 22 ms 19044 KB Output is correct
13 Correct 26 ms 19468 KB Output is correct
14 Correct 6 ms 14420 KB Output is correct
15 Correct 7 ms 14588 KB Output is correct
16 Correct 171 ms 44832 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 6 ms 14316 KB Output is correct
19 Correct 6 ms 14292 KB Output is correct
20 Correct 6 ms 14376 KB Output is correct
21 Correct 7 ms 14292 KB Output is correct
22 Correct 6 ms 14292 KB Output is correct
23 Correct 415 ms 71256 KB Output is correct
24 Correct 6 ms 14292 KB Output is correct
25 Correct 9 ms 14672 KB Output is correct
26 Correct 8 ms 14712 KB Output is correct
27 Correct 12 ms 14824 KB Output is correct
28 Correct 145 ms 36732 KB Output is correct
29 Correct 218 ms 48296 KB Output is correct
30 Correct 347 ms 59504 KB Output is correct
31 Correct 410 ms 71340 KB Output is correct
32 Correct 6 ms 14292 KB Output is correct
33 Correct 6 ms 14292 KB Output is correct
34 Correct 7 ms 14292 KB Output is correct
35 Correct 6 ms 14292 KB Output is correct
36 Correct 6 ms 14292 KB Output is correct
37 Correct 6 ms 14364 KB Output is correct
38 Correct 6 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 14296 KB Output is correct
42 Correct 6 ms 14292 KB Output is correct
43 Correct 7 ms 14548 KB Output is correct
44 Correct 8 ms 14680 KB Output is correct
45 Correct 197 ms 42376 KB Output is correct
46 Correct 293 ms 56136 KB Output is correct
47 Correct 313 ms 56076 KB Output is correct
48 Correct 6 ms 14292 KB Output is correct
49 Correct 6 ms 14292 KB Output is correct
50 Correct 7 ms 14380 KB Output is correct
51 Correct 7 ms 14292 KB Output is correct
52 Correct 7 ms 14292 KB Output is correct
53 Correct 6 ms 14292 KB Output is correct
54 Correct 7 ms 14292 KB Output is correct
55 Incorrect 3119 ms 59140 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 14304 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14328 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 175 ms 44816 KB Output is correct
10 Correct 20 ms 17520 KB Output is correct
11 Correct 64 ms 30672 KB Output is correct
12 Correct 22 ms 19044 KB Output is correct
13 Correct 26 ms 19468 KB Output is correct
14 Correct 6 ms 14420 KB Output is correct
15 Correct 7 ms 14588 KB Output is correct
16 Correct 171 ms 44832 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 6 ms 14360 KB Output is correct
19 Correct 6 ms 14292 KB Output is correct
20 Correct 484 ms 68488 KB Output is correct
21 Correct 520 ms 68320 KB Output is correct
22 Correct 526 ms 68276 KB Output is correct
23 Correct 416 ms 67144 KB Output is correct
24 Correct 242 ms 32272 KB Output is correct
25 Correct 283 ms 36980 KB Output is correct
26 Correct 232 ms 37108 KB Output is correct
27 Correct 515 ms 75436 KB Output is correct
28 Correct 446 ms 75376 KB Output is correct
29 Correct 447 ms 75376 KB Output is correct
30 Correct 505 ms 75408 KB Output is correct
31 Correct 6 ms 14292 KB Output is correct
32 Correct 29 ms 18420 KB Output is correct
33 Correct 77 ms 23380 KB Output is correct
34 Correct 418 ms 68592 KB Output is correct
35 Correct 13 ms 15572 KB Output is correct
36 Correct 47 ms 19968 KB Output is correct
37 Correct 94 ms 25600 KB Output is correct
38 Correct 155 ms 37016 KB Output is correct
39 Correct 249 ms 44780 KB Output is correct
40 Correct 298 ms 54312 KB Output is correct
41 Correct 407 ms 62164 KB Output is correct
42 Correct 516 ms 69988 KB Output is correct
43 Correct 6 ms 14292 KB Output is correct
44 Correct 6 ms 14292 KB Output is correct
45 Correct 6 ms 14292 KB Output is correct
46 Correct 6 ms 14376 KB Output is correct
47 Correct 7 ms 14296 KB Output is correct
48 Correct 7 ms 14360 KB Output is correct
49 Correct 6 ms 14384 KB Output is correct
50 Correct 7 ms 14292 KB Output is correct
51 Correct 7 ms 14292 KB Output is correct
52 Correct 7 ms 14292 KB Output is correct
53 Correct 6 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 181 ms 42440 KB Output is correct
57 Correct 288 ms 56132 KB Output is correct
58 Correct 279 ms 56144 KB Output is correct
59 Correct 11 ms 14292 KB Output is correct
60 Correct 8 ms 14316 KB Output is correct
61 Correct 9 ms 14292 KB Output is correct
62 Correct 412 ms 75484 KB Output is correct
63 Correct 428 ms 75420 KB Output is correct
64 Correct 408 ms 75120 KB Output is correct
65 Correct 9 ms 14804 KB Output is correct
66 Correct 12 ms 15304 KB Output is correct
67 Correct 183 ms 42068 KB Output is correct
68 Correct 302 ms 57080 KB Output is correct
69 Correct 456 ms 70276 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 14304 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14328 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 175 ms 44816 KB Output is correct
10 Correct 20 ms 17520 KB Output is correct
11 Correct 64 ms 30672 KB Output is correct
12 Correct 22 ms 19044 KB Output is correct
13 Correct 26 ms 19468 KB Output is correct
14 Correct 6 ms 14420 KB Output is correct
15 Correct 7 ms 14588 KB Output is correct
16 Correct 171 ms 44832 KB Output is correct
17 Correct 444 ms 75880 KB Output is correct
18 Correct 422 ms 76012 KB Output is correct
19 Correct 417 ms 68312 KB Output is correct
20 Correct 423 ms 68728 KB Output is correct
21 Correct 378 ms 66032 KB Output is correct
22 Correct 7 ms 14292 KB Output is correct
23 Correct 61 ms 23564 KB Output is correct
24 Correct 22 ms 16684 KB Output is correct
25 Correct 66 ms 22888 KB Output is correct
26 Correct 117 ms 28224 KB Output is correct
27 Correct 193 ms 42448 KB Output is correct
28 Correct 275 ms 50384 KB Output is correct
29 Correct 331 ms 57544 KB Output is correct
30 Correct 379 ms 63924 KB Output is correct
31 Correct 449 ms 70612 KB Output is correct
32 Correct 433 ms 71344 KB Output is correct
33 Correct 426 ms 75496 KB Output is correct
34 Correct 9 ms 14932 KB Output is correct
35 Correct 12 ms 15488 KB Output is correct
36 Correct 181 ms 42188 KB Output is correct
37 Correct 298 ms 57412 KB Output is correct
38 Correct 431 ms 70524 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 14304 KB Output is correct
5 Correct 6 ms 14292 KB Output is correct
6 Correct 6 ms 14328 KB Output is correct
7 Correct 6 ms 14292 KB Output is correct
8 Correct 7 ms 14292 KB Output is correct
9 Correct 175 ms 44816 KB Output is correct
10 Correct 20 ms 17520 KB Output is correct
11 Correct 64 ms 30672 KB Output is correct
12 Correct 22 ms 19044 KB Output is correct
13 Correct 26 ms 19468 KB Output is correct
14 Correct 6 ms 14420 KB Output is correct
15 Correct 7 ms 14588 KB Output is correct
16 Correct 171 ms 44832 KB Output is correct
17 Correct 6 ms 14292 KB Output is correct
18 Correct 6 ms 14316 KB Output is correct
19 Correct 6 ms 14292 KB Output is correct
20 Correct 6 ms 14376 KB Output is correct
21 Correct 7 ms 14292 KB Output is correct
22 Correct 6 ms 14292 KB Output is correct
23 Correct 415 ms 71256 KB Output is correct
24 Correct 6 ms 14292 KB Output is correct
25 Correct 9 ms 14672 KB Output is correct
26 Correct 8 ms 14712 KB Output is correct
27 Correct 12 ms 14824 KB Output is correct
28 Correct 145 ms 36732 KB Output is correct
29 Correct 218 ms 48296 KB Output is correct
30 Correct 347 ms 59504 KB Output is correct
31 Correct 410 ms 71340 KB Output is correct
32 Correct 6 ms 14292 KB Output is correct
33 Correct 6 ms 14292 KB Output is correct
34 Correct 7 ms 14292 KB Output is correct
35 Correct 6 ms 14292 KB Output is correct
36 Correct 6 ms 14292 KB Output is correct
37 Correct 6 ms 14364 KB Output is correct
38 Correct 6 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 14296 KB Output is correct
42 Correct 6 ms 14292 KB Output is correct
43 Correct 7 ms 14548 KB Output is correct
44 Correct 8 ms 14680 KB Output is correct
45 Correct 197 ms 42376 KB Output is correct
46 Correct 293 ms 56136 KB Output is correct
47 Correct 313 ms 56076 KB Output is correct
48 Correct 6 ms 14292 KB Output is correct
49 Correct 6 ms 14292 KB Output is correct
50 Correct 7 ms 14380 KB Output is correct
51 Correct 7 ms 14292 KB Output is correct
52 Correct 7 ms 14292 KB Output is correct
53 Correct 6 ms 14292 KB Output is correct
54 Correct 7 ms 14292 KB Output is correct
55 Incorrect 3119 ms 59140 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -