oj.uz

Submission #1053276

# Submission time Handle Problem Language Result Execution time Memory
1053276 2024-08-11T10:13:22 Z dozer Fountain Parks (IOI21_parks) C++17
55 / 100
 1845 ms 138820 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define st first
#define nd second
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define N 300005


const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;


int par[N], sz[N], TOT;
pii rev[N];

int find(int node){
	if (par[node] == node) return node;
	return par[node] = find(par[node]);
}


void uni(int a, int b){
	a = find(a), b = find(b);
	if (a == b) return;
	TOT--;
	if (sz[a] < sz[b]) swap(a, b);
	par[b] = a;
	sz[a] += b;
}


int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
		build({}, {}, {}, {});
	    return 1;
    }
    map<pii ,int> ind;
    int n = x.size();
    for (int i = 0; i < n; i++){
    	ind[{x[i], y[i]}] = i;
    	sz[i] = 1, par[i] = i;
    }

    vector<pii> dir = {{0, -2}, {-2, 0}, {0, 2}, {2, 0}};

    vector<pii> edges, b1, b2;
    map<pii, int> cnt;
    map<pii, set<int>> rev2;

    int cntr = 0;
    for (int i = 0; i < n; i++){
    	int a = x[i], b = y[i];
    	for (auto k : dir){
    		int c = a + k.st, d = b + k.nd;
    		if (ind.count({c, d}) && ind[{c, d}] > i){
    			int g = (a + c) / 2, h = (b + d) / 2;
    			pii f1, f2;
    			if (b == d){
    				f1 = {g, h + 1};
    				f2 = {g, h - 1};
    			}
    			else{
    				f1 = {g + 1, h};
    				f2 = {g - 1, h};
    			}
    			edges.pb({i, ind[{c, d}]});
    			b1.pb(f1);
    			b2.pb(f2);
    			rev2[f1].insert(cntr);
    			rev2[f2].insert(cntr);
    			cnt[f1]++;
    			cnt[f2]++;
    			cntr++;
    		}
    	}
    }

    queue<int> q;
    for (int i = 0; i < cntr; i++){
    	if (cnt[b1[i]] == 1 || cnt[b2[i]] == 1) q.push(i);
    }

 	vector<int> u, v, a, b;
    
    set<int> undone;

    for (int i = 0; i < cntr; i++) undone.insert(i);
    TOT = n;
	while(TOT > 1){
		 while(!q.empty()){
	    	int top = q.front();
	    	q.pop();
	    	
	    	if (undone.count(top) == 0) continue;
	    	
	    	pii todo = {-1, -1};
	    	if (cnt[b1[top]] == 1) todo = b1[top];
	    	else if (cnt[b2[top]] == 1) todo = b2[top];
	    	if (todo.st == -1) continue;

	    	a.pb(todo.st), b.pb(todo.nd);
	    	vector<pii> V = {b1[top], b2[top]};
	    	for (auto i : V){
	    		cnt[i]--;
	    		rev2[i].erase(top);
	    		if (rev2[i].size()){
	    			q.push(*rev2[i].begin());
	    		}
	    	}

	    	u.pb(edges[top].st);
	    	v.pb(edges[top].nd);
	    	uni(edges[top].st, edges[top].nd);
	    	undone.erase(top);
	    }	

	    if (TOT == 1) break;

	    auto it = undone.begin();
	    while(it != undone.end()){
	    	int i = *it;
	    	if (find(edges[i].st) == find(edges[i].nd)) it = undone.erase(it); 
	    	else if (cnt[b1[i]] == 0 && cnt[b2[i]] == 0) it = undone.erase(it);
	    	else break;
	    }

	    if (undone.empty()) break;
		int tmp = *undone.begin();
		cnt[b1[tmp]] = 1;
		q.push(tmp);
	}

	
	if (TOT == 1){
		build(u, v, a, b);
		return 1;
	}
   
   return 0;
}

/*
static void check(bool cond, string message) {
	if (!cond) {
		printf("%s\n", message.c_str());
		fclose(stdout);
		exit(0);
	}
}

static int n;
static bool build_called;
static int m;
static vector<int> _u, _v, _a, _b;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
	check(!build_called, "build is called more than once");
	build_called = true;
	m = u.size();
	check(int(v.size()) == m, "u.size() != v.size()");
	check(int(a.size()) == m, "u.size() != a.size()");
	check(int(b.size()) == m, "u.size() != b.size()");
	_u = u;
	_v = v;
	_a = a;
	_b = b;
}

int main() {
	fileio();
	assert(scanf("%d", &n) == 1);
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	build_called = false;
	const int possible = construct_roads(x, y);

	check(possible == 0 || possible == 1, "Invalid return value of construct_roads()");
	if (possible == 1) {
		check(build_called, "construct_roads() returned 1 without calling build()");
	} else {
		check(!build_called, "construct_roads() called build() but returned 0");
	}

	printf("%d\n", possible);
	if (possible == 1) {
		printf("%d\n", m);
		for (int j = 0; j < m; j++) {
			printf("%d %d %d %d\n", _u[j], _v[j], _a[j], _b[j]);
		}
	}
	fclose(stdout);
	return 0;
}
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 457 ms 63504 KB Output is correct
10 Correct 22 ms 8280 KB Output is correct
11 Correct 126 ms 34112 KB Output is correct
12 Correct 28 ms 10860 KB Output is correct
13 Correct 104 ms 27748 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 4 ms 3544 KB Output is correct
16 Correct 444 ms 63508 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 457 ms 63504 KB Output is correct
10 Correct 22 ms 8280 KB Output is correct
11 Correct 126 ms 34112 KB Output is correct
12 Correct 28 ms 10860 KB Output is correct
13 Correct 104 ms 27748 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 4 ms 3544 KB Output is correct
16 Correct 444 ms 63508 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct
23 Correct 1775 ms 138820 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Correct 4 ms 3164 KB Output is correct
26 Correct 10 ms 4188 KB Output is correct
27 Correct 13 ms 4952 KB Output is correct
28 Correct 505 ms 53852 KB Output is correct
29 Correct 916 ms 81444 KB Output is correct
30 Correct 1329 ms 107556 KB Output is correct
31 Correct 1804 ms 138516 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 0 ms 2396 KB Output is correct
35 Correct 0 ms 2396 KB Output is correct
36 Correct 0 ms 2396 KB Output is correct
37 Correct 0 ms 2396 KB Output is correct
38 Correct 0 ms 2396 KB Output is correct
39 Correct 1 ms 2392 KB Output is correct
40 Correct 0 ms 2396 KB Output is correct
41 Correct 0 ms 2396 KB Output is correct
42 Correct 0 ms 2396 KB Output is correct
43 Correct 5 ms 3420 KB Output is correct
44 Correct 7 ms 3932 KB Output is correct
45 Correct 504 ms 53656 KB Output is correct
46 Correct 820 ms 79080 KB Output is correct
47 Correct 823 ms 79144 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 457 ms 63504 KB Output is correct
10 Correct 22 ms 8280 KB Output is correct
11 Correct 126 ms 34112 KB Output is correct
12 Correct 28 ms 10860 KB Output is correct
13 Correct 104 ms 27748 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 4 ms 3544 KB Output is correct
16 Correct 444 ms 63508 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct
23 Correct 1775 ms 138820 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Correct 4 ms 3164 KB Output is correct
26 Correct 10 ms 4188 KB Output is correct
27 Correct 13 ms 4952 KB Output is correct
28 Correct 505 ms 53852 KB Output is correct
29 Correct 916 ms 81444 KB Output is correct
30 Correct 1329 ms 107556 KB Output is correct
31 Correct 1804 ms 138516 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 0 ms 2396 KB Output is correct
35 Correct 0 ms 2396 KB Output is correct
36 Correct 0 ms 2396 KB Output is correct
37 Correct 0 ms 2396 KB Output is correct
38 Correct 0 ms 2396 KB Output is correct
39 Correct 1 ms 2392 KB Output is correct
40 Correct 0 ms 2396 KB Output is correct
41 Correct 0 ms 2396 KB Output is correct
42 Correct 0 ms 2396 KB Output is correct
43 Correct 5 ms 3420 KB Output is correct
44 Correct 7 ms 3932 KB Output is correct
45 Correct 504 ms 53656 KB Output is correct
46 Correct 820 ms 79080 KB Output is correct
47 Correct 823 ms 79144 KB Output is correct
48 Correct 1 ms 2392 KB Output is correct
49 Correct 0 ms 2396 KB Output is correct
50 Correct 0 ms 2396 KB Output is correct
51 Correct 0 ms 2396 KB Output is correct
52 Correct 0 ms 2396 KB Output is correct
53 Correct 1 ms 2396 KB Output is correct
54 Correct 1 ms 2396 KB Output is correct
55 Incorrect 1845 ms 128756 KB Tree @(5, 84071) appears more than once: for edges on positions 133523 and 134076
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 457 ms 63504 KB Output is correct
10 Correct 22 ms 8280 KB Output is correct
11 Correct 126 ms 34112 KB Output is correct
12 Correct 28 ms 10860 KB Output is correct
13 Correct 104 ms 27748 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 4 ms 3544 KB Output is correct
16 Correct 444 ms 63508 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 945 ms 94428 KB Output is correct
21 Correct 1020 ms 94500 KB Output is correct
22 Correct 1022 ms 94560 KB Output is correct
23 Correct 982 ms 108488 KB Output is correct
24 Correct 223 ms 18000 KB Output is correct
25 Correct 1292 ms 120604 KB Output is correct
26 Correct 1356 ms 120356 KB Output is correct
27 Correct 1423 ms 127052 KB Output is correct
28 Correct 1305 ms 126900 KB Output is correct
29 Correct 1422 ms 127216 KB Output is correct
30 Correct 1315 ms 127200 KB Output is correct
31 Correct 1 ms 2396 KB Output is correct
32 Correct 50 ms 9168 KB Output is correct
33 Correct 75 ms 10308 KB Output is correct
34 Correct 985 ms 94588 KB Output is correct
35 Correct 32 ms 7004 KB Output is correct
36 Correct 218 ms 25020 KB Output is correct
37 Correct 596 ms 48576 KB Output is correct
38 Correct 407 ms 39984 KB Output is correct
39 Correct 660 ms 55376 KB Output is correct
40 Correct 936 ms 72128 KB Output is correct
41 Correct 1105 ms 86312 KB Output is correct
42 Correct 1395 ms 100560 KB Output is correct
43 Correct 0 ms 2396 KB Output is correct
44 Correct 0 ms 2396 KB Output is correct
45 Correct 0 ms 2396 KB Output is correct
46 Correct 0 ms 2396 KB Output is correct
47 Correct 0 ms 2396 KB Output is correct
48 Correct 1 ms 2396 KB Output is correct
49 Correct 0 ms 2396 KB Output is correct
50 Correct 0 ms 2396 KB Output is correct
51 Correct 0 ms 2396 KB Output is correct
52 Correct 0 ms 2396 KB Output is correct
53 Correct 0 ms 2396 KB Output is correct
54 Correct 4 ms 3420 KB Output is correct
55 Correct 7 ms 3932 KB Output is correct
56 Correct 578 ms 53636 KB Output is correct
57 Correct 878 ms 79140 KB Output is correct
58 Correct 895 ms 79144 KB Output is correct
59 Correct 1 ms 2392 KB Output is correct
60 Correct 0 ms 2396 KB Output is correct
61 Correct 0 ms 2396 KB Output is correct
62 Correct 1190 ms 126672 KB Output is correct
63 Correct 1138 ms 126852 KB Output is correct
64 Correct 1213 ms 126208 KB Output is correct
65 Correct 10 ms 4188 KB Output is correct
66 Correct 21 ms 6236 KB Output is correct
67 Correct 529 ms 52764 KB Output is correct
68 Correct 909 ms 80368 KB Output is correct
69 Correct 1381 ms 106020 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 457 ms 63504 KB Output is correct
10 Correct 22 ms 8280 KB Output is correct
11 Correct 126 ms 34112 KB Output is correct
12 Correct 28 ms 10860 KB Output is correct
13 Correct 104 ms 27748 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 4 ms 3544 KB Output is correct
16 Correct 444 ms 63508 KB Output is correct
17 Correct 1127 ms 126756 KB Output is correct
18 Correct 1093 ms 125228 KB Output is correct
19 Correct 976 ms 94504 KB Output is correct
20 Correct 1483 ms 116244 KB Output is correct
21 Correct 1212 ms 110116 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Correct 129 ms 17984 KB Output is correct
24 Correct 77 ms 12744 KB Output is correct
25 Correct 378 ms 38744 KB Output is correct
26 Correct 811 ms 65588 KB Output is correct
27 Correct 651 ms 56884 KB Output is correct
28 Correct 909 ms 72336 KB Output is correct
29 Correct 1128 ms 85484 KB Output is correct
30 Correct 1378 ms 98828 KB Output is correct
31 Correct 1703 ms 111956 KB Output is correct
32 Correct 1551 ms 123176 KB Output is correct
33 Correct 1177 ms 126640 KB Output is correct
34 Correct 19 ms 4952 KB Output is correct
35 Correct 26 ms 7260 KB Output is correct
36 Correct 620 ms 57136 KB Output is correct
37 Correct 1036 ms 85800 KB Output is correct
38 Correct 1578 ms 113700 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 457 ms 63504 KB Output is correct
10 Correct 22 ms 8280 KB Output is correct
11 Correct 126 ms 34112 KB Output is correct
12 Correct 28 ms 10860 KB Output is correct
13 Correct 104 ms 27748 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 4 ms 3544 KB Output is correct
16 Correct 444 ms 63508 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 0 ms 2396 KB Output is correct
23 Correct 1775 ms 138820 KB Output is correct
24 Correct 1 ms 2392 KB Output is correct
25 Correct 4 ms 3164 KB Output is correct
26 Correct 10 ms 4188 KB Output is correct
27 Correct 13 ms 4952 KB Output is correct
28 Correct 505 ms 53852 KB Output is correct
29 Correct 916 ms 81444 KB Output is correct
30 Correct 1329 ms 107556 KB Output is correct
31 Correct 1804 ms 138516 KB Output is correct
32 Correct 1 ms 2396 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 0 ms 2396 KB Output is correct
35 Correct 0 ms 2396 KB Output is correct
36 Correct 0 ms 2396 KB Output is correct
37 Correct 0 ms 2396 KB Output is correct
38 Correct 0 ms 2396 KB Output is correct
39 Correct 1 ms 2392 KB Output is correct
40 Correct 0 ms 2396 KB Output is correct
41 Correct 0 ms 2396 KB Output is correct
42 Correct 0 ms 2396 KB Output is correct
43 Correct 5 ms 3420 KB Output is correct
44 Correct 7 ms 3932 KB Output is correct
45 Correct 504 ms 53656 KB Output is correct
46 Correct 820 ms 79080 KB Output is correct
47 Correct 823 ms 79144 KB Output is correct
48 Correct 1 ms 2392 KB Output is correct
49 Correct 0 ms 2396 KB Output is correct
50 Correct 0 ms 2396 KB Output is correct
51 Correct 0 ms 2396 KB Output is correct
52 Correct 0 ms 2396 KB Output is correct
53 Correct 1 ms 2396 KB Output is correct
54 Correct 1 ms 2396 KB Output is correct
55 Incorrect 1845 ms 128756 KB Tree @(5, 84071) appears more than once: for edges on positions 133523 and 134076
56 Halted 0 ms 0 KB -