oj.uz

Submission #435590

# Submission time Handle Problem Language Result Execution time Memory
435590 2021-06-23T12:54:48 Z PinkRabbit Fountain Parks (IOI21_parks) C++17
55 / 100
 959 ms 109156 KB 
// PinkRabbit

#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
#include <random>
#include <chrono>

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
inline T range(T l, T r) {
	return std::uniform_int_distribution<T>(l, r)(rng);
}

template<typename T>
inline void vec2arr(std::vector<T> v, T *arr, T bias = 0) {
	int n = (int)v.size();
	for (int i = 1; i <= n; ++i)
		arr[i] = v[i - 1] + bias;
}
template<typename T>
inline std::vector<T> arr2vec(T *arr, int n, T bias = 0) {
	std::vector<T> v(n);
	for (int i = 1; i <= n; ++i)
		v[i - 1] = arr[i] + bias;
	return v;
}

typedef std::vector<int> VI;
const int MN = 800005;
const int MV = 400005;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

int N;
int x[MN], y[MN];
int ndir[MN][4], edir[MN][4];
std::map<int, int> mp[MV];
int eu[MN * 2], ev[MN * 2], M;

int per[MN * 2], iper[MN * 2];
int AnsU[MN], AnsV[MN], AnsA[MN], AnsB[MN];
int pa[MN];
int fp(int u) {
	return pa[u] ? pa[u] = fp(pa[u]) : u;
}
inline bool GenTree() {
	int tot = 0;
	std::shuffle(per + 1, per + M + 1, rng);
	for (int i = 1; i <= M; ++i)
		iper[i] = 0;
	for (int id = 1; id <= M; ++id) {
		int u = eu[per[id]], v = ev[per[id]];
		int pu = fp(u), pv = fp(v);
		if (pu != pv) {
			++tot;
			AnsU[tot] = u;
			AnsV[tot] = v;
			pa[pu] = pv;
			iper[per[id]] = tot;
		}
	}
	return tot == N - 1;
}

VI G[MN];
int bel[MN], scnt;
int dfn[MN], low[MN], dfc;
int stk[MN], top;
bool instk[MN];
void Tarjan(int u) {
	dfn[u] = low[u] = ++dfc;
	instk[stk[++top] = u] = true;
	for (int v : G[u]) {
		if (!dfn[v]) {
			Tarjan(v);
			low[u] = std::min(low[u], low[v]);
		} else if (instk[v])
			low[u] = std::min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u]) {
		++scnt;
		while (true) {
			int w = stk[top--];
			instk[w] = false;
			bel[w] = scnt;
//			printf("bel[%d] = %d\n", w, scnt);
			if (w == u)
				break;
		}
	}
}
inline bool Solve() {
	for (int i = 1; i <= 2 * (N - 1); ++i)
		G[i].clear(), dfn[i] = low[i] = 0;
	auto AddE = [&](int u, int tu, int v, int tv) -> void {
		if (!u || !v || !iper[u] || !iper[v])
			return ;
//		printf("([(%d, %d) - (%d, %d)], %d) <---> ([(%d, %d) - (%d, %d)], %d)\n", 2 * x[eu[u]], 2 * y[eu[u]], 2 * x[ev[u]], 2 * y[ev[u]], tu, 2 * x[eu[v]], 2 * y[eu[v]], 2 * x[ev[v]], 2 * y[ev[v]], tv);
		u = iper[u], v = iper[v];
		G[u + (tu ? N - 1 : 0)].push_back(v + (tv ? 0 : N - 1));
		G[v + (tv ? N - 1 : 0)].push_back(u + (tu ? 0 : N - 1));
	};
	for (int i = 1; i <= N; ++i) {
		AddE(edir[i][0], 1, edir[i][1], 1);
		AddE(edir[i][1], 0, edir[i][2], 1);
		AddE(edir[i][2], 0, edir[i][3], 0);
		AddE(edir[i][3], 1, edir[i][0], 0);
		if (ndir[i][0] && ndir[i][1] && ndir[ndir[i][0]][1]) {
			AddE(edir[i][0], 1, edir[ndir[i][1]][0], 0);
			AddE(edir[i][1], 1, edir[ndir[i][0]][1], 0);
		}
	}
	scnt = 0;
	for (int u = 1; u <= 2 * (N - 1); ++u)
		if (!dfn[u])
			Tarjan(u);
	for (int i = 1; i <= N - 1; ++i) {
		if (bel[i] == bel[i + N - 1])
			return false;
		int d = bel[i + N - 1] < bel[i];
		AnsA[i] = x[AnsU[i]] + x[AnsV[i]];
		AnsB[i] = y[AnsU[i]] + y[AnsV[i]];
		if (x[AnsU[i]] == x[AnsV[i]])
			AnsA[i] += (d ? 1 : -1);
		if (y[AnsU[i]] == y[AnsV[i]])
			AnsB[i] += (d ? 1 : -1);
	}
	build(arr2vec(AnsU, N - 1, -1), arr2vec(AnsV, N - 1, -1), arr2vec(AnsA, N - 1), arr2vec(AnsB, N - 1));
	return true;
}

int construct_roads(VI t_x, VI t_y) {
	clock_t tstart = clock();
	N = (int)t_x.size();
	vec2arr(t_x, x);
	vec2arr(t_y, y);
	for (int i = 1; i <= N; ++i) {
		x[i] /= 2;
		y[i] /= 2;
		mp[x[i]][y[i]] = i;
	}
	for (int i = 1; i <= N; ++i) {
		for (int d = 0; d < 2; ++d) {
			int nx = x[i] + dx[d];
			int ny = y[i] + dy[d];
			auto it = mp[nx].find(ny);
			if (it != mp[nx].end()) {
				++M;
				eu[M] = i;
				ev[M] = it -> second;
				if (rng() & 1)
					std::swap(eu[M], ev[M]);
				ndir[i][d] = it->second;
				ndir[it->second][d ^ 2] = i;
				edir[i][d] = M;
				edir[it->second][d ^ 2] = M;
			}
		}
	}
	for (int i = 1; i <= M; ++i)
		per[i] = i;
	if (!GenTree())
		return 0;
	if (Solve())
		return 1;
	while ((clock() - tstart) / (double)CLOCKS_PER_SEC < 2.7) {
		GenTree();
		if (Solve())
			return 1;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37844 KB Output is correct
2 Correct 30 ms 37900 KB Output is correct
3 Correct 25 ms 37836 KB Output is correct
4 Correct 26 ms 37964 KB Output is correct
5 Correct 25 ms 37984 KB Output is correct
6 Correct 28 ms 37860 KB Output is correct
7 Correct 25 ms 37844 KB Output is correct
8 Correct 26 ms 37964 KB Output is correct
9 Correct 284 ms 58540 KB Output is correct
10 Correct 42 ms 40012 KB Output is correct
11 Correct 87 ms 49032 KB Output is correct
12 Correct 38 ms 41040 KB Output is correct
13 Correct 53 ms 43580 KB Output is correct
14 Correct 36 ms 38052 KB Output is correct
15 Correct 27 ms 38088 KB Output is correct
16 Correct 180 ms 58616 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37844 KB Output is correct
2 Correct 30 ms 37900 KB Output is correct
3 Correct 25 ms 37836 KB Output is correct
4 Correct 26 ms 37964 KB Output is correct
5 Correct 25 ms 37984 KB Output is correct
6 Correct 28 ms 37860 KB Output is correct
7 Correct 25 ms 37844 KB Output is correct
8 Correct 26 ms 37964 KB Output is correct
9 Correct 284 ms 58540 KB Output is correct
10 Correct 42 ms 40012 KB Output is correct
11 Correct 87 ms 49032 KB Output is correct
12 Correct 38 ms 41040 KB Output is correct
13 Correct 53 ms 43580 KB Output is correct
14 Correct 36 ms 38052 KB Output is correct
15 Correct 27 ms 38088 KB Output is correct
16 Correct 180 ms 58616 KB Output is correct
17 Correct 22 ms 37964 KB Output is correct
18 Correct 25 ms 37956 KB Output is correct
19 Correct 25 ms 37916 KB Output is correct
20 Correct 27 ms 37964 KB Output is correct
21 Correct 24 ms 37840 KB Output is correct
22 Correct 25 ms 37888 KB Output is correct
23 Correct 849 ms 89040 KB Output is correct
24 Correct 32 ms 37964 KB Output is correct
25 Correct 34 ms 38200 KB Output is correct
26 Correct 31 ms 38340 KB Output is correct
27 Correct 34 ms 38468 KB Output is correct
28 Correct 213 ms 58256 KB Output is correct
29 Correct 395 ms 68556 KB Output is correct
30 Correct 533 ms 78764 KB Output is correct
31 Correct 818 ms 88968 KB Output is correct
32 Correct 30 ms 37964 KB Output is correct
33 Correct 27 ms 37896 KB Output is correct
34 Correct 26 ms 37940 KB Output is correct
35 Correct 29 ms 37900 KB Output is correct
36 Correct 29 ms 37880 KB Output is correct
37 Correct 30 ms 38004 KB Output is correct
38 Correct 30 ms 37964 KB Output is correct
39 Correct 28 ms 37868 KB Output is correct
40 Correct 25 ms 37980 KB Output is correct
41 Correct 29 ms 37808 KB Output is correct
42 Correct 30 ms 38016 KB Output is correct
43 Correct 32 ms 38160 KB Output is correct
44 Correct 29 ms 38220 KB Output is correct
45 Correct 294 ms 62460 KB Output is correct
46 Correct 456 ms 73624 KB Output is correct
47 Correct 399 ms 73624 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37844 KB Output is correct
2 Correct 30 ms 37900 KB Output is correct
3 Correct 25 ms 37836 KB Output is correct
4 Correct 26 ms 37964 KB Output is correct
5 Correct 25 ms 37984 KB Output is correct
6 Correct 28 ms 37860 KB Output is correct
7 Correct 25 ms 37844 KB Output is correct
8 Correct 26 ms 37964 KB Output is correct
9 Correct 284 ms 58540 KB Output is correct
10 Correct 42 ms 40012 KB Output is correct
11 Correct 87 ms 49032 KB Output is correct
12 Correct 38 ms 41040 KB Output is correct
13 Correct 53 ms 43580 KB Output is correct
14 Correct 36 ms 38052 KB Output is correct
15 Correct 27 ms 38088 KB Output is correct
16 Correct 180 ms 58616 KB Output is correct
17 Correct 22 ms 37964 KB Output is correct
18 Correct 25 ms 37956 KB Output is correct
19 Correct 25 ms 37916 KB Output is correct
20 Correct 27 ms 37964 KB Output is correct
21 Correct 24 ms 37840 KB Output is correct
22 Correct 25 ms 37888 KB Output is correct
23 Correct 849 ms 89040 KB Output is correct
24 Correct 32 ms 37964 KB Output is correct
25 Correct 34 ms 38200 KB Output is correct
26 Correct 31 ms 38340 KB Output is correct
27 Correct 34 ms 38468 KB Output is correct
28 Correct 213 ms 58256 KB Output is correct
29 Correct 395 ms 68556 KB Output is correct
30 Correct 533 ms 78764 KB Output is correct
31 Correct 818 ms 88968 KB Output is correct
32 Correct 30 ms 37964 KB Output is correct
33 Correct 27 ms 37896 KB Output is correct
34 Correct 26 ms 37940 KB Output is correct
35 Correct 29 ms 37900 KB Output is correct
36 Correct 29 ms 37880 KB Output is correct
37 Correct 30 ms 38004 KB Output is correct
38 Correct 30 ms 37964 KB Output is correct
39 Correct 28 ms 37868 KB Output is correct
40 Correct 25 ms 37980 KB Output is correct
41 Correct 29 ms 37808 KB Output is correct
42 Correct 30 ms 38016 KB Output is correct
43 Correct 32 ms 38160 KB Output is correct
44 Correct 29 ms 38220 KB Output is correct
45 Correct 294 ms 62460 KB Output is correct
46 Correct 456 ms 73624 KB Output is correct
47 Correct 399 ms 73624 KB Output is correct
48 Correct 27 ms 37964 KB Output is correct
49 Correct 27 ms 37964 KB Output is correct
50 Correct 28 ms 37904 KB Output is correct
51 Correct 28 ms 37988 KB Output is correct
52 Correct 27 ms 37964 KB Output is correct
53 Correct 29 ms 37928 KB Output is correct
54 Correct 29 ms 37924 KB Output is correct
55 Incorrect 959 ms 90888 KB Tree @(5, 12645) appears more than once: for edges on positions 588 and 666
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37844 KB Output is correct
2 Correct 30 ms 37900 KB Output is correct
3 Correct 25 ms 37836 KB Output is correct
4 Correct 26 ms 37964 KB Output is correct
5 Correct 25 ms 37984 KB Output is correct
6 Correct 28 ms 37860 KB Output is correct
7 Correct 25 ms 37844 KB Output is correct
8 Correct 26 ms 37964 KB Output is correct
9 Correct 284 ms 58540 KB Output is correct
10 Correct 42 ms 40012 KB Output is correct
11 Correct 87 ms 49032 KB Output is correct
12 Correct 38 ms 41040 KB Output is correct
13 Correct 53 ms 43580 KB Output is correct
14 Correct 36 ms 38052 KB Output is correct
15 Correct 27 ms 38088 KB Output is correct
16 Correct 180 ms 58616 KB Output is correct
17 Correct 29 ms 38092 KB Output is correct
18 Correct 27 ms 37960 KB Output is correct
19 Correct 29 ms 37880 KB Output is correct
20 Correct 653 ms 109156 KB Output is correct
21 Correct 635 ms 99260 KB Output is correct
22 Correct 609 ms 98832 KB Output is correct
23 Correct 334 ms 73448 KB Output is correct
24 Correct 304 ms 52000 KB Output is correct
25 Correct 381 ms 63772 KB Output is correct
26 Correct 285 ms 63768 KB Output is correct
27 Correct 381 ms 79336 KB Output is correct
28 Correct 391 ms 79424 KB Output is correct
29 Correct 497 ms 79608 KB Output is correct
30 Correct 436 ms 79404 KB Output is correct
31 Correct 27 ms 37964 KB Output is correct
32 Correct 52 ms 41592 KB Output is correct
33 Correct 91 ms 44896 KB Output is correct
34 Correct 672 ms 105220 KB Output is correct
35 Correct 36 ms 39244 KB Output is correct
36 Correct 71 ms 44360 KB Output is correct
37 Correct 141 ms 50828 KB Output is correct
38 Correct 199 ms 58928 KB Output is correct
39 Correct 281 ms 66740 KB Output is correct
40 Correct 425 ms 74604 KB Output is correct
41 Correct 576 ms 82620 KB Output is correct
42 Correct 659 ms 90448 KB Output is correct
43 Correct 28 ms 37964 KB Output is correct
44 Correct 28 ms 37920 KB Output is correct
45 Correct 27 ms 37964 KB Output is correct
46 Correct 28 ms 37900 KB Output is correct
47 Correct 28 ms 37852 KB Output is correct
48 Correct 27 ms 37932 KB Output is correct
49 Correct 26 ms 37908 KB Output is correct
50 Correct 31 ms 37964 KB Output is correct
51 Correct 33 ms 37892 KB Output is correct
52 Correct 28 ms 37836 KB Output is correct
53 Correct 27 ms 37964 KB Output is correct
54 Correct 28 ms 38180 KB Output is correct
55 Correct 32 ms 38220 KB Output is correct
56 Correct 270 ms 62536 KB Output is correct
57 Correct 399 ms 73680 KB Output is correct
58 Correct 436 ms 73624 KB Output is correct
59 Correct 27 ms 37836 KB Output is correct
60 Correct 28 ms 37964 KB Output is correct
61 Correct 28 ms 37836 KB Output is correct
62 Correct 472 ms 79380 KB Output is correct
63 Correct 390 ms 79396 KB Output is correct
64 Correct 425 ms 79132 KB Output is correct
65 Correct 28 ms 38464 KB Output is correct
66 Correct 33 ms 38972 KB Output is correct
67 Correct 259 ms 62768 KB Output is correct
68 Correct 437 ms 75372 KB Output is correct
69 Correct 652 ms 87748 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37844 KB Output is correct
2 Correct 30 ms 37900 KB Output is correct
3 Correct 25 ms 37836 KB Output is correct
4 Correct 26 ms 37964 KB Output is correct
5 Correct 25 ms 37984 KB Output is correct
6 Correct 28 ms 37860 KB Output is correct
7 Correct 25 ms 37844 KB Output is correct
8 Correct 26 ms 37964 KB Output is correct
9 Correct 284 ms 58540 KB Output is correct
10 Correct 42 ms 40012 KB Output is correct
11 Correct 87 ms 49032 KB Output is correct
12 Correct 38 ms 41040 KB Output is correct
13 Correct 53 ms 43580 KB Output is correct
14 Correct 36 ms 38052 KB Output is correct
15 Correct 27 ms 38088 KB Output is correct
16 Correct 180 ms 58616 KB Output is correct
17 Correct 399 ms 79848 KB Output is correct
18 Correct 372 ms 79888 KB Output is correct
19 Correct 587 ms 106968 KB Output is correct
20 Correct 643 ms 88596 KB Output is correct
21 Correct 435 ms 78512 KB Output is correct
22 Correct 27 ms 37964 KB Output is correct
23 Correct 86 ms 46184 KB Output is correct
24 Correct 45 ms 40540 KB Output is correct
25 Correct 101 ms 47172 KB Output is correct
26 Correct 213 ms 53768 KB Output is correct
27 Correct 299 ms 64036 KB Output is correct
28 Correct 370 ms 70792 KB Output is correct
29 Correct 473 ms 77276 KB Output is correct
30 Correct 589 ms 83544 KB Output is correct
31 Correct 657 ms 90248 KB Output is correct
32 Correct 669 ms 86692 KB Output is correct
33 Correct 481 ms 79352 KB Output is correct
34 Correct 32 ms 38528 KB Output is correct
35 Correct 35 ms 39116 KB Output is correct
36 Correct 319 ms 62760 KB Output is correct
37 Correct 493 ms 75296 KB Output is correct
38 Correct 718 ms 87944 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37844 KB Output is correct
2 Correct 30 ms 37900 KB Output is correct
3 Correct 25 ms 37836 KB Output is correct
4 Correct 26 ms 37964 KB Output is correct
5 Correct 25 ms 37984 KB Output is correct
6 Correct 28 ms 37860 KB Output is correct
7 Correct 25 ms 37844 KB Output is correct
8 Correct 26 ms 37964 KB Output is correct
9 Correct 284 ms 58540 KB Output is correct
10 Correct 42 ms 40012 KB Output is correct
11 Correct 87 ms 49032 KB Output is correct
12 Correct 38 ms 41040 KB Output is correct
13 Correct 53 ms 43580 KB Output is correct
14 Correct 36 ms 38052 KB Output is correct
15 Correct 27 ms 38088 KB Output is correct
16 Correct 180 ms 58616 KB Output is correct
17 Correct 22 ms 37964 KB Output is correct
18 Correct 25 ms 37956 KB Output is correct
19 Correct 25 ms 37916 KB Output is correct
20 Correct 27 ms 37964 KB Output is correct
21 Correct 24 ms 37840 KB Output is correct
22 Correct 25 ms 37888 KB Output is correct
23 Correct 849 ms 89040 KB Output is correct
24 Correct 32 ms 37964 KB Output is correct
25 Correct 34 ms 38200 KB Output is correct
26 Correct 31 ms 38340 KB Output is correct
27 Correct 34 ms 38468 KB Output is correct
28 Correct 213 ms 58256 KB Output is correct
29 Correct 395 ms 68556 KB Output is correct
30 Correct 533 ms 78764 KB Output is correct
31 Correct 818 ms 88968 KB Output is correct
32 Correct 30 ms 37964 KB Output is correct
33 Correct 27 ms 37896 KB Output is correct
34 Correct 26 ms 37940 KB Output is correct
35 Correct 29 ms 37900 KB Output is correct
36 Correct 29 ms 37880 KB Output is correct
37 Correct 30 ms 38004 KB Output is correct
38 Correct 30 ms 37964 KB Output is correct
39 Correct 28 ms 37868 KB Output is correct
40 Correct 25 ms 37980 KB Output is correct
41 Correct 29 ms 37808 KB Output is correct
42 Correct 30 ms 38016 KB Output is correct
43 Correct 32 ms 38160 KB Output is correct
44 Correct 29 ms 38220 KB Output is correct
45 Correct 294 ms 62460 KB Output is correct
46 Correct 456 ms 73624 KB Output is correct
47 Correct 399 ms 73624 KB Output is correct
48 Correct 27 ms 37964 KB Output is correct
49 Correct 27 ms 37964 KB Output is correct
50 Correct 28 ms 37904 KB Output is correct
51 Correct 28 ms 37988 KB Output is correct
52 Correct 27 ms 37964 KB Output is correct
53 Correct 29 ms 37928 KB Output is correct
54 Correct 29 ms 37924 KB Output is correct
55 Incorrect 959 ms 90888 KB Tree @(5, 12645) appears more than once: for edges on positions 588 and 666
56 Halted 0 ms 0 KB -