oj.uz

Submission #617892

# Submission time Handle Problem Language Result Execution time Memory
617892 2022-08-01T16:25:53 Z amunduzbaev Fountain Parks (IOI21_parks) C++17
25 / 100
 974 ms 61208 KB 
#include "parks.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
typedef long long ll;

const int N = 2e5 + 5;
vector<ar<int, 3>> edges[N];

int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	map<ar<int, 2>, int> ss, mm;
	for(int i=0;i<n;i++){
		ss[{x[i], y[i]}] = i;
	}
	
	vector<ar<int, 2>> e, p;
	
	auto add = [&](int a, int b, int p1, int p2){
		edges[a].push_back({b, p1, p2});
		edges[b].push_back({a, p1, p2});
	};
	
	vector<int> par(n), sz(n, 1);
	iota(par.begin(), par.end(), 0);
	function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
	auto merge = [&](int a, int b){
		a = f(a), b = f(b);
		if(a == b) return false;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a, sz[a] += sz[b];
		return true;
	};
	
	for(int i=0;i<n;i++){
		if(ss.count({x[i] - 2, y[i]})){
			int j = ss[{x[i] - 2, y[i]}];
			if(!merge(i, j)) continue;
			e.push_back({i, j});
			p.push_back({-1, -1});
			int u = e.size() - 1;
			if(mm.count({x[i] - 1, y[i] - 1})){
				int v = mm[{x[i] - 1, y[i] - 1}];
				add(u, v, x[i] - 1, y[i] - 1);
				mm.erase({x[i] - 1, y[i] - 1});
			} else {
				mm[{x[i] - 1, y[i] - 1}] = u;
			}
			if(mm.count({x[i] - 1, y[i] + 1})){
				int v = mm[{x[i] - 1, y[i] + 1}];
				add(u, v, x[i] - 1, y[i] + 1);
				mm.erase({x[i] - 1, y[i] + 1});
			} else {
				mm[{x[i] - 1, y[i] + 1}] = u;
			}
		}
		
		if(ss.count({x[i], y[i] - 2})){
			int j = ss[{x[i], y[i] - 2}];
			if(!merge(i, j)) continue;
			e.push_back({i, j});
			p.push_back({-1, -1});
			int u = e.size() - 1;
			if(mm.count({x[i] - 1, y[i] - 1})){
				int v = mm[{x[i] - 1, y[i] - 1}];
				add(u, v, x[i] - 1, y[i] - 1);
				mm.erase({x[i] - 1, y[i] - 1});
			} else {
				mm[{x[i] - 1, y[i] - 1}] = u;
			}
			if(mm.count({x[i] + 1, y[i] - 1})){
				int v = mm[{x[i] + 1, y[i] - 1}];
				add(u, v, x[i] + 1, y[i] - 1);
				mm.erase({x[i] + 1, y[i] - 1});
			} else {
				mm[{x[i] + 1, y[i] - 1}] = u;
			}
		}
	}
	
	if(sz[f(0)] != n) {
		//~ assert(false);
		return 0;
	}
	int m = e.size();
	
	vector<int> used(m);
	function<void(int)> dfs = [&](int i){
		used[i] = 1;
		for(auto [x, p1, p2] : edges[i]){
			if(used[x]) continue;
			p[x] = {p1, p2};
			dfs(x);
		}
	};
	for(auto [x, i] : mm){
		if(used[i]) continue;
		p[i] = x;
		dfs(i);
	}
	
	for(int i=0;i<m;i++){
		if(used[i]) continue;
		p[i] = {edges[i].back()[1], edges[i].back()[2]};
		edges[i].pop_back();
		
		dfs(i);
	}
	
	vector<int> u(m), v(m), A(m), B(m);
	for(int i=0;i<m;i++){
		u[i] = e[i][0], v[i] = e[i][1];
		A[i] = p[i][0], B[i] = p[i][1];
	}
	
	build(u, v, A, B);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 344 ms 33644 KB Output is correct
10 Correct 18 ms 7776 KB Output is correct
11 Correct 103 ms 20292 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 84 ms 15420 KB Output is correct
14 Correct 6 ms 5136 KB Output is correct
15 Correct 5 ms 5416 KB Output is correct
16 Correct 324 ms 33504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 344 ms 33644 KB Output is correct
10 Correct 18 ms 7776 KB Output is correct
11 Correct 103 ms 20292 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 84 ms 15420 KB Output is correct
14 Correct 6 ms 5136 KB Output is correct
15 Correct 5 ms 5416 KB Output is correct
16 Correct 324 ms 33504 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Incorrect 3 ms 4948 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 344 ms 33644 KB Output is correct
10 Correct 18 ms 7776 KB Output is correct
11 Correct 103 ms 20292 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 84 ms 15420 KB Output is correct
14 Correct 6 ms 5136 KB Output is correct
15 Correct 5 ms 5416 KB Output is correct
16 Correct 324 ms 33504 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Incorrect 3 ms 4948 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 344 ms 33644 KB Output is correct
10 Correct 18 ms 7776 KB Output is correct
11 Correct 103 ms 20292 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 84 ms 15420 KB Output is correct
14 Correct 6 ms 5136 KB Output is correct
15 Correct 5 ms 5416 KB Output is correct
16 Correct 324 ms 33504 KB Output is correct
17 Correct 4 ms 5004 KB Output is correct
18 Correct 3 ms 4968 KB Output is correct
19 Correct 3 ms 5000 KB Output is correct
20 Correct 779 ms 55756 KB Output is correct
21 Correct 864 ms 51688 KB Output is correct
22 Correct 805 ms 49260 KB Output is correct
23 Correct 721 ms 52892 KB Output is correct
24 Correct 313 ms 22812 KB Output is correct
25 Correct 898 ms 50820 KB Output is correct
26 Correct 819 ms 50948 KB Output is correct
27 Correct 856 ms 61128 KB Output is correct
28 Correct 852 ms 60988 KB Output is correct
29 Correct 880 ms 61164 KB Output is correct
30 Correct 905 ms 60980 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Correct 35 ms 8364 KB Output is correct
33 Correct 103 ms 14120 KB Output is correct
34 Correct 801 ms 57856 KB Output is correct
35 Correct 20 ms 6740 KB Output is correct
36 Correct 129 ms 13284 KB Output is correct
37 Correct 383 ms 21248 KB Output is correct
38 Correct 274 ms 22144 KB Output is correct
39 Correct 405 ms 28380 KB Output is correct
40 Correct 619 ms 34620 KB Output is correct
41 Correct 800 ms 40840 KB Output is correct
42 Correct 974 ms 46980 KB Output is correct
43 Correct 3 ms 4948 KB Output is correct
44 Correct 3 ms 4948 KB Output is correct
45 Correct 3 ms 4948 KB Output is correct
46 Correct 3 ms 4996 KB Output is correct
47 Correct 3 ms 5000 KB Output is correct
48 Correct 3 ms 4948 KB Output is correct
49 Correct 3 ms 4976 KB Output is correct
50 Correct 3 ms 4948 KB Output is correct
51 Correct 3 ms 4996 KB Output is correct
52 Correct 2 ms 4948 KB Output is correct
53 Correct 3 ms 4948 KB Output is correct
54 Correct 6 ms 5332 KB Output is correct
55 Correct 7 ms 5560 KB Output is correct
56 Correct 373 ms 28392 KB Output is correct
57 Correct 621 ms 38684 KB Output is correct
58 Correct 587 ms 38704 KB Output is correct
59 Correct 3 ms 4948 KB Output is correct
60 Correct 3 ms 4948 KB Output is correct
61 Correct 3 ms 4948 KB Output is correct
62 Correct 835 ms 61056 KB Output is correct
63 Correct 853 ms 61208 KB Output is correct
64 Correct 840 ms 60716 KB Output is correct
65 Correct 9 ms 5716 KB Output is correct
66 Correct 16 ms 6420 KB Output is correct
67 Correct 359 ms 27684 KB Output is correct
68 Correct 597 ms 38712 KB Output is correct
69 Correct 926 ms 50000 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 344 ms 33644 KB Output is correct
10 Correct 18 ms 7776 KB Output is correct
11 Correct 103 ms 20292 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 84 ms 15420 KB Output is correct
14 Correct 6 ms 5136 KB Output is correct
15 Correct 5 ms 5416 KB Output is correct
16 Correct 324 ms 33504 KB Output is correct
17 Correct 839 ms 61148 KB Output is correct
18 Correct 821 ms 61044 KB Output is correct
19 Correct 823 ms 56716 KB Output is correct
20 Correct 833 ms 46676 KB Output is correct
21 Correct 786 ms 48300 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Incorrect 68 ms 10528 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 344 ms 33644 KB Output is correct
10 Correct 18 ms 7776 KB Output is correct
11 Correct 103 ms 20292 KB Output is correct
12 Correct 27 ms 9292 KB Output is correct
13 Correct 84 ms 15420 KB Output is correct
14 Correct 6 ms 5136 KB Output is correct
15 Correct 5 ms 5416 KB Output is correct
16 Correct 324 ms 33504 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Incorrect 3 ms 4948 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 2
19 Halted 0 ms 0 KB -