oj.uz

Submission #446628

# Submission time Handle Problem Language Result Execution time Memory
446628 2021-07-22T20:42:16 Z LucaDantas Fountain Parks (IOI21_parks) C++17
55 / 100
 1431 ms 126704 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }

void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)

#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define ff first
#define ss second

constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 8e5 + 10;

mt19937 rng(random_device{}());

struct DSU {
	int pai[maxn], peso[maxn], qtd;
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		--qtd;
		if(peso[a] < peso[b]) swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
} dsu;

vector<int> pt[maxn], g[maxn];

int match[maxn];
bool mark[maxn];

int t, n, qtd_ruas;

bool dfs(int u) {
	mark[u] = 1;
	if(u >= qtd_ruas) return (match[u] == -1 ? 1 : dfs(match[u]));

	for(int v : g[u]) {
		if(mark[v] || !dfs(v)) continue;
		match[u] = v; match[v] = u;
		return 1;
	}

	return 0;
}

struct Road { // todas as ruas possiveis
	int x, y, tipo; // ponto inicial da rua e se é vertical ou horizontal
} ruas[maxn];

pii conecta[maxn];

struct Banco {
	int x, y;
} bancos[maxn];

map<pair<int,int>, int> mp; // salva o id dos pontos

inline void add(int a, int b) { g[a].pb(b), g[b].pb(a); }

int get(pii p) { 
	if(mp.count(p)) return mp[p];
	bancos[t] = {p.ff, p.ss};
	return mp[p] = t++;
}

int construct_roads(vector<int> x, vector<int> y) {
	n = sz(x); dsu.qtd = n;
	for(int i = 0; i < n; i++)
		mp[pii(x[i], y[i])] = i;
	for(int i = 0; i < n; i++) {
		if(mp.count({x[i]+2, y[i]})) {
			conecta[t] = {i, mp[pii(x[i]+2, y[i])]};
			ruas[t++] = {x[i], y[i], 0}; // 0 == horizontal
			dsu.join(i, mp[pii(x[i]+2, y[i])]);
		}
		if(mp.count({x[i], y[i]+2})) {
			conecta[t] = {i, mp[pii(x[i], y[i]+2)]};
			ruas[t++] = {x[i], y[i], 1}; // 1 == vertical
			dsu.join(i, mp[pii(x[i], y[i]+2)]);
		}
	}
	if(dsu.qtd != 1) return 0; // impossivel, o grafo completo não é conexo
	
	qtd_ruas = t;
	for(int i = 0; i < qtd_ruas; i++) {
		auto [X, Y, tipo] = ruas[i];
		// db(X, Y, tipo);
		if(!tipo) {
			int aq = get({X+1, Y+1});
			add(i, aq);
			
			// db(pii(X, Y), tipo, aq);

			aq = get({X+1, Y-1});
			add(i, aq);
			// db(pii(X, Y), tipo, aq);
		} else {
			int aq = get({X+1, Y+1});
			add(i, aq);
			// db(pii(X, Y), tipo, aq);

			aq = get({X-1, Y+1});
			add(i, aq);
			// db(pii(X, Y), tipo, aq);
		}
	}

	int ans = 0;
	memset(match, -1, sizeof match);

	vector<int> p(qtd_ruas); iota(all(p), 0);

	for(int i = 0; i < t; i++)
		shuffle(all(g[i]), rng);

	for(int antes = -1; ans != antes;) {
		antes = ans;
		memset(mark, 0, sizeof mark);
		shuffle(all(p), rng);
		for(int i = 0; i < qtd_ruas; i++)
			if(!mark[p[i]] && match[p[i]] == -1 && dfs(p[i])) ++ans;
		// db("OPA", ans, antes);
	}

	// db(ans);

	/* for(int i = 0; i < qtd_ruas; i++)
		db(i, match[i], bancos[match[i]].x, bancos[match[i]].y); */

	if(ans != qtd_ruas) return 0;
	
	vector<int> u(qtd_ruas), v(qtd_ruas), a(qtd_ruas), b(qtd_ruas);

	for(int i = 0; i < qtd_ruas; i++) {
		u[i] = conecta[i].ff, v[i] = conecta[i].ss;
		a[i] = bancos[match[i]].x, b[i] = bancos[match[i]].y;
	}
	build(u, v, a, b);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47940 KB Output is correct
2 Correct 31 ms 48064 KB Output is correct
3 Correct 27 ms 44140 KB Output is correct
4 Correct 27 ms 47956 KB Output is correct
5 Correct 28 ms 47976 KB Output is correct
6 Correct 26 ms 44132 KB Output is correct
7 Correct 26 ms 44108 KB Output is correct
8 Correct 25 ms 44100 KB Output is correct
9 Correct 386 ms 86412 KB Output is correct
10 Correct 50 ms 52028 KB Output is correct
11 Correct 186 ms 68724 KB Output is correct
12 Correct 63 ms 53956 KB Output is correct
13 Correct 64 ms 48436 KB Output is correct
14 Correct 31 ms 44236 KB Output is correct
15 Correct 31 ms 44276 KB Output is correct
16 Correct 385 ms 86340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47940 KB Output is correct
2 Correct 31 ms 48064 KB Output is correct
3 Correct 27 ms 44140 KB Output is correct
4 Correct 27 ms 47956 KB Output is correct
5 Correct 28 ms 47976 KB Output is correct
6 Correct 26 ms 44132 KB Output is correct
7 Correct 26 ms 44108 KB Output is correct
8 Correct 25 ms 44100 KB Output is correct
9 Correct 386 ms 86412 KB Output is correct
10 Correct 50 ms 52028 KB Output is correct
11 Correct 186 ms 68724 KB Output is correct
12 Correct 63 ms 53956 KB Output is correct
13 Correct 64 ms 48436 KB Output is correct
14 Correct 31 ms 44236 KB Output is correct
15 Correct 31 ms 44276 KB Output is correct
16 Correct 385 ms 86340 KB Output is correct
17 Correct 28 ms 47964 KB Output is correct
18 Correct 27 ms 47964 KB Output is correct
19 Correct 27 ms 47968 KB Output is correct
20 Correct 28 ms 47952 KB Output is correct
21 Correct 26 ms 44056 KB Output is correct
22 Correct 28 ms 48064 KB Output is correct
23 Correct 1391 ms 126704 KB Output is correct
24 Correct 32 ms 48076 KB Output is correct
25 Correct 32 ms 48528 KB Output is correct
26 Correct 28 ms 44372 KB Output is correct
27 Correct 30 ms 44488 KB Output is correct
28 Correct 452 ms 79328 KB Output is correct
29 Correct 773 ms 95624 KB Output is correct
30 Correct 1092 ms 111744 KB Output is correct
31 Correct 1431 ms 126436 KB Output is correct
32 Correct 29 ms 47944 KB Output is correct
33 Correct 27 ms 47960 KB Output is correct
34 Correct 27 ms 47936 KB Output is correct
35 Correct 25 ms 44108 KB Output is correct
36 Correct 25 ms 44044 KB Output is correct
37 Correct 27 ms 48072 KB Output is correct
38 Correct 27 ms 47948 KB Output is correct
39 Correct 28 ms 47940 KB Output is correct
40 Correct 27 ms 47976 KB Output is correct
41 Correct 25 ms 44128 KB Output is correct
42 Correct 28 ms 47956 KB Output is correct
43 Correct 27 ms 44236 KB Output is correct
44 Correct 28 ms 44352 KB Output is correct
45 Correct 427 ms 80096 KB Output is correct
46 Correct 656 ms 94616 KB Output is correct
47 Correct 715 ms 94576 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47940 KB Output is correct
2 Correct 31 ms 48064 KB Output is correct
3 Correct 27 ms 44140 KB Output is correct
4 Correct 27 ms 47956 KB Output is correct
5 Correct 28 ms 47976 KB Output is correct
6 Correct 26 ms 44132 KB Output is correct
7 Correct 26 ms 44108 KB Output is correct
8 Correct 25 ms 44100 KB Output is correct
9 Correct 386 ms 86412 KB Output is correct
10 Correct 50 ms 52028 KB Output is correct
11 Correct 186 ms 68724 KB Output is correct
12 Correct 63 ms 53956 KB Output is correct
13 Correct 64 ms 48436 KB Output is correct
14 Correct 31 ms 44236 KB Output is correct
15 Correct 31 ms 44276 KB Output is correct
16 Correct 385 ms 86340 KB Output is correct
17 Correct 28 ms 47964 KB Output is correct
18 Correct 27 ms 47964 KB Output is correct
19 Correct 27 ms 47968 KB Output is correct
20 Correct 28 ms 47952 KB Output is correct
21 Correct 26 ms 44056 KB Output is correct
22 Correct 28 ms 48064 KB Output is correct
23 Correct 1391 ms 126704 KB Output is correct
24 Correct 32 ms 48076 KB Output is correct
25 Correct 32 ms 48528 KB Output is correct
26 Correct 28 ms 44372 KB Output is correct
27 Correct 30 ms 44488 KB Output is correct
28 Correct 452 ms 79328 KB Output is correct
29 Correct 773 ms 95624 KB Output is correct
30 Correct 1092 ms 111744 KB Output is correct
31 Correct 1431 ms 126436 KB Output is correct
32 Correct 29 ms 47944 KB Output is correct
33 Correct 27 ms 47960 KB Output is correct
34 Correct 27 ms 47936 KB Output is correct
35 Correct 25 ms 44108 KB Output is correct
36 Correct 25 ms 44044 KB Output is correct
37 Correct 27 ms 48072 KB Output is correct
38 Correct 27 ms 47948 KB Output is correct
39 Correct 28 ms 47940 KB Output is correct
40 Correct 27 ms 47976 KB Output is correct
41 Correct 25 ms 44128 KB Output is correct
42 Correct 28 ms 47956 KB Output is correct
43 Correct 27 ms 44236 KB Output is correct
44 Correct 28 ms 44352 KB Output is correct
45 Correct 427 ms 80096 KB Output is correct
46 Correct 656 ms 94616 KB Output is correct
47 Correct 715 ms 94576 KB Output is correct
48 Correct 27 ms 47952 KB Output is correct
49 Correct 27 ms 48016 KB Output is correct
50 Correct 27 ms 47944 KB Output is correct
51 Correct 28 ms 47944 KB Output is correct
52 Correct 28 ms 48056 KB Output is correct
53 Correct 28 ms 48076 KB Output is correct
54 Correct 28 ms 48064 KB Output is correct
55 Incorrect 1365 ms 109248 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 27 ms 47940 KB Output is correct
2 Correct 31 ms 48064 KB Output is correct
3 Correct 27 ms 44140 KB Output is correct
4 Correct 27 ms 47956 KB Output is correct
5 Correct 28 ms 47976 KB Output is correct
6 Correct 26 ms 44132 KB Output is correct
7 Correct 26 ms 44108 KB Output is correct
8 Correct 25 ms 44100 KB Output is correct
9 Correct 386 ms 86412 KB Output is correct
10 Correct 50 ms 52028 KB Output is correct
11 Correct 186 ms 68724 KB Output is correct
12 Correct 63 ms 53956 KB Output is correct
13 Correct 64 ms 48436 KB Output is correct
14 Correct 31 ms 44236 KB Output is correct
15 Correct 31 ms 44276 KB Output is correct
16 Correct 385 ms 86340 KB Output is correct
17 Correct 27 ms 48032 KB Output is correct
18 Correct 27 ms 48024 KB Output is correct
19 Correct 26 ms 44044 KB Output is correct
20 Correct 1031 ms 107776 KB Output is correct
21 Correct 1232 ms 106888 KB Output is correct
22 Correct 1081 ms 106416 KB Output is correct
23 Correct 807 ms 113400 KB Output is correct
24 Correct 322 ms 59844 KB Output is correct
25 Correct 466 ms 63612 KB Output is correct
26 Correct 430 ms 64056 KB Output is correct
27 Correct 1036 ms 124816 KB Output is correct
28 Correct 1028 ms 124668 KB Output is correct
29 Correct 1065 ms 124740 KB Output is correct
30 Correct 1026 ms 124776 KB Output is correct
31 Correct 28 ms 48076 KB Output is correct
32 Correct 71 ms 52736 KB Output is correct
33 Correct 138 ms 51956 KB Output is correct
34 Correct 1272 ms 106972 KB Output is correct
35 Correct 37 ms 45176 KB Output is correct
36 Correct 94 ms 48936 KB Output is correct
37 Correct 241 ms 53832 KB Output is correct
38 Correct 373 ms 72324 KB Output is correct
39 Correct 522 ms 81092 KB Output is correct
40 Correct 813 ms 90140 KB Output is correct
41 Correct 904 ms 99268 KB Output is correct
42 Correct 1110 ms 108300 KB Output is correct
43 Correct 28 ms 48040 KB Output is correct
44 Correct 27 ms 48044 KB Output is correct
45 Correct 28 ms 47980 KB Output is correct
46 Correct 27 ms 44144 KB Output is correct
47 Correct 25 ms 44100 KB Output is correct
48 Correct 28 ms 48076 KB Output is correct
49 Correct 27 ms 48048 KB Output is correct
50 Correct 28 ms 47948 KB Output is correct
51 Correct 28 ms 47948 KB Output is correct
52 Correct 26 ms 44108 KB Output is correct
53 Correct 27 ms 47988 KB Output is correct
54 Correct 26 ms 44236 KB Output is correct
55 Correct 28 ms 44348 KB Output is correct
56 Correct 447 ms 80096 KB Output is correct
57 Correct 773 ms 94520 KB Output is correct
58 Correct 656 ms 94532 KB Output is correct
59 Correct 26 ms 44108 KB Output is correct
60 Correct 28 ms 48016 KB Output is correct
61 Correct 26 ms 44088 KB Output is correct
62 Correct 887 ms 124820 KB Output is correct
63 Correct 986 ms 124796 KB Output is correct
64 Correct 963 ms 124420 KB Output is correct
65 Correct 29 ms 44468 KB Output is correct
66 Correct 33 ms 44912 KB Output is correct
67 Correct 424 ms 79516 KB Output is correct
68 Correct 749 ms 95428 KB Output is correct
69 Correct 1016 ms 111160 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47940 KB Output is correct
2 Correct 31 ms 48064 KB Output is correct
3 Correct 27 ms 44140 KB Output is correct
4 Correct 27 ms 47956 KB Output is correct
5 Correct 28 ms 47976 KB Output is correct
6 Correct 26 ms 44132 KB Output is correct
7 Correct 26 ms 44108 KB Output is correct
8 Correct 25 ms 44100 KB Output is correct
9 Correct 386 ms 86412 KB Output is correct
10 Correct 50 ms 52028 KB Output is correct
11 Correct 186 ms 68724 KB Output is correct
12 Correct 63 ms 53956 KB Output is correct
13 Correct 64 ms 48436 KB Output is correct
14 Correct 31 ms 44236 KB Output is correct
15 Correct 31 ms 44276 KB Output is correct
16 Correct 385 ms 86340 KB Output is correct
17 Correct 951 ms 124832 KB Output is correct
18 Correct 1032 ms 125004 KB Output is correct
19 Correct 1362 ms 113604 KB Output is correct
20 Correct 1415 ms 116792 KB Output is correct
21 Correct 983 ms 113456 KB Output is correct
22 Correct 29 ms 47948 KB Output is correct
23 Correct 139 ms 58112 KB Output is correct
24 Correct 51 ms 46160 KB Output is correct
25 Correct 150 ms 51220 KB Output is correct
26 Correct 249 ms 56208 KB Output is correct
27 Correct 572 ms 81348 KB Output is correct
28 Correct 752 ms 89676 KB Output is correct
29 Correct 912 ms 98064 KB Output is correct
30 Correct 1077 ms 106492 KB Output is correct
31 Correct 1221 ms 114832 KB Output is correct
32 Correct 1122 ms 120644 KB Output is correct
33 Correct 880 ms 124756 KB Output is correct
34 Correct 30 ms 44620 KB Output is correct
35 Correct 35 ms 45020 KB Output is correct
36 Correct 472 ms 81620 KB Output is correct
37 Correct 787 ms 98548 KB Output is correct
38 Correct 1088 ms 115300 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 47940 KB Output is correct
2 Correct 31 ms 48064 KB Output is correct
3 Correct 27 ms 44140 KB Output is correct
4 Correct 27 ms 47956 KB Output is correct
5 Correct 28 ms 47976 KB Output is correct
6 Correct 26 ms 44132 KB Output is correct
7 Correct 26 ms 44108 KB Output is correct
8 Correct 25 ms 44100 KB Output is correct
9 Correct 386 ms 86412 KB Output is correct
10 Correct 50 ms 52028 KB Output is correct
11 Correct 186 ms 68724 KB Output is correct
12 Correct 63 ms 53956 KB Output is correct
13 Correct 64 ms 48436 KB Output is correct
14 Correct 31 ms 44236 KB Output is correct
15 Correct 31 ms 44276 KB Output is correct
16 Correct 385 ms 86340 KB Output is correct
17 Correct 28 ms 47964 KB Output is correct
18 Correct 27 ms 47964 KB Output is correct
19 Correct 27 ms 47968 KB Output is correct
20 Correct 28 ms 47952 KB Output is correct
21 Correct 26 ms 44056 KB Output is correct
22 Correct 28 ms 48064 KB Output is correct
23 Correct 1391 ms 126704 KB Output is correct
24 Correct 32 ms 48076 KB Output is correct
25 Correct 32 ms 48528 KB Output is correct
26 Correct 28 ms 44372 KB Output is correct
27 Correct 30 ms 44488 KB Output is correct
28 Correct 452 ms 79328 KB Output is correct
29 Correct 773 ms 95624 KB Output is correct
30 Correct 1092 ms 111744 KB Output is correct
31 Correct 1431 ms 126436 KB Output is correct
32 Correct 29 ms 47944 KB Output is correct
33 Correct 27 ms 47960 KB Output is correct
34 Correct 27 ms 47936 KB Output is correct
35 Correct 25 ms 44108 KB Output is correct
36 Correct 25 ms 44044 KB Output is correct
37 Correct 27 ms 48072 KB Output is correct
38 Correct 27 ms 47948 KB Output is correct
39 Correct 28 ms 47940 KB Output is correct
40 Correct 27 ms 47976 KB Output is correct
41 Correct 25 ms 44128 KB Output is correct
42 Correct 28 ms 47956 KB Output is correct
43 Correct 27 ms 44236 KB Output is correct
44 Correct 28 ms 44352 KB Output is correct
45 Correct 427 ms 80096 KB Output is correct
46 Correct 656 ms 94616 KB Output is correct
47 Correct 715 ms 94576 KB Output is correct
48 Correct 27 ms 47952 KB Output is correct
49 Correct 27 ms 48016 KB Output is correct
50 Correct 27 ms 47944 KB Output is correct
51 Correct 28 ms 47944 KB Output is correct
52 Correct 28 ms 48056 KB Output is correct
53 Correct 28 ms 48076 KB Output is correct
54 Correct 28 ms 48064 KB Output is correct
55 Incorrect 1365 ms 109248 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -