oj.uz

Submission #1053289

# Submission time Handle Problem Language Result Execution time Memory
1053289 2024-08-11T10:17:41 Z dozer Fountain Parks (IOI21_parks) C++17
55 / 100
 2509 ms 140596 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 (auto k : dir){
	    for (int i = 0; i < n; i++){
	    	int a = x[i], b = y[i];
    		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;
}
*/

Compilation message

parks.cpp:152:13: warning: 'void check(bool, std::string)' defined but not used [-Wunused-function]
  152 | static void check(bool cond, string message) {
      |             ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 2480 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 512 ms 63708 KB Output is correct
10 Correct 18 ms 8232 KB Output is correct
11 Correct 128 ms 34088 KB Output is correct
12 Correct 29 ms 10928 KB Output is correct
13 Correct 98 ms 27708 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 4 ms 3420 KB Output is correct
16 Correct 487 ms 63496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 2480 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 512 ms 63708 KB Output is correct
10 Correct 18 ms 8232 KB Output is correct
11 Correct 128 ms 34088 KB Output is correct
12 Correct 29 ms 10928 KB Output is correct
13 Correct 98 ms 27708 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 4 ms 3420 KB Output is correct
16 Correct 487 ms 63496 KB Output is correct
17 Correct 0 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 0 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 2032 ms 140596 KB Output is correct
24 Correct 1 ms 2396 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 4776 KB Output is correct
28 Correct 626 ms 51288 KB Output is correct
29 Correct 993 ms 80168 KB Output is correct
30 Correct 1480 ms 106788 KB Output is correct
31 Correct 2255 ms 140224 KB Output is correct
32 Correct 0 ms 2484 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 0 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 0 ms 2396 KB Output is correct
40 Correct 0 ms 2396 KB Output is correct
41 Correct 0 ms 2396 KB Output is correct
42 Correct 1 ms 2396 KB Output is correct
43 Correct 4 ms 3420 KB Output is correct
44 Correct 7 ms 3676 KB Output is correct
45 Correct 533 ms 52052 KB Output is correct
46 Correct 906 ms 77392 KB Output is correct
47 Correct 982 ms 77352 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 2480 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 512 ms 63708 KB Output is correct
10 Correct 18 ms 8232 KB Output is correct
11 Correct 128 ms 34088 KB Output is correct
12 Correct 29 ms 10928 KB Output is correct
13 Correct 98 ms 27708 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 4 ms 3420 KB Output is correct
16 Correct 487 ms 63496 KB Output is correct
17 Correct 0 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 0 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 2032 ms 140596 KB Output is correct
24 Correct 1 ms 2396 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 4776 KB Output is correct
28 Correct 626 ms 51288 KB Output is correct
29 Correct 993 ms 80168 KB Output is correct
30 Correct 1480 ms 106788 KB Output is correct
31 Correct 2255 ms 140224 KB Output is correct
32 Correct 0 ms 2484 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 0 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 0 ms 2396 KB Output is correct
40 Correct 0 ms 2396 KB Output is correct
41 Correct 0 ms 2396 KB Output is correct
42 Correct 1 ms 2396 KB Output is correct
43 Correct 4 ms 3420 KB Output is correct
44 Correct 7 ms 3676 KB Output is correct
45 Correct 533 ms 52052 KB Output is correct
46 Correct 906 ms 77392 KB Output is correct
47 Correct 982 ms 77352 KB Output is correct
48 Correct 0 ms 2396 KB Output is correct
49 Correct 0 ms 2492 KB Output is correct
50 Correct 0 ms 2396 KB Output is correct
51 Correct 1 ms 2392 KB Output is correct
52 Correct 0 ms 2396 KB Output is correct
53 Correct 0 ms 2396 KB Output is correct
54 Correct 0 ms 2396 KB Output is correct
55 Incorrect 2509 ms 132192 KB Tree @(5, 130541) appears more than once: for edges on positions 149015 and 166682
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 2480 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 512 ms 63708 KB Output is correct
10 Correct 18 ms 8232 KB Output is correct
11 Correct 128 ms 34088 KB Output is correct
12 Correct 29 ms 10928 KB Output is correct
13 Correct 98 ms 27708 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 4 ms 3420 KB Output is correct
16 Correct 487 ms 63496 KB Output is correct
17 Correct 0 ms 2392 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 1366 ms 94260 KB Output is correct
21 Correct 1197 ms 94500 KB Output is correct
22 Correct 1155 ms 94384 KB Output is correct
23 Correct 932 ms 108840 KB Output is correct
24 Correct 214 ms 18136 KB Output is correct
25 Correct 1201 ms 120756 KB Output is correct
26 Correct 1224 ms 120248 KB Output is correct
27 Correct 1276 ms 127012 KB Output is correct
28 Correct 1259 ms 127016 KB Output is correct
29 Correct 1248 ms 127140 KB Output is correct
30 Correct 1205 ms 127280 KB Output is correct
31 Correct 0 ms 2396 KB Output is correct
32 Correct 47 ms 9104 KB Output is correct
33 Correct 99 ms 10076 KB Output is correct
34 Correct 1096 ms 94540 KB Output is correct
35 Correct 31 ms 6992 KB Output is correct
36 Correct 204 ms 25400 KB Output is correct
37 Correct 507 ms 48360 KB Output is correct
38 Correct 399 ms 40500 KB Output is correct
39 Correct 621 ms 55852 KB Output is correct
40 Correct 892 ms 72080 KB Output is correct
41 Correct 1158 ms 86308 KB Output is correct
42 Correct 1452 ms 100236 KB Output is correct
43 Correct 0 ms 2392 KB Output is correct
44 Correct 0 ms 2396 KB Output is correct
45 Correct 0 ms 2644 KB Output is correct
46 Correct 0 ms 2396 KB Output is correct
47 Correct 0 ms 2396 KB Output is correct
48 Correct 0 ms 2396 KB Output is correct
49 Correct 0 ms 2396 KB Output is correct
50 Correct 0 ms 2400 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 3324 KB Output is correct
55 Correct 7 ms 3676 KB Output is correct
56 Correct 533 ms 52140 KB Output is correct
57 Correct 919 ms 77348 KB Output is correct
58 Correct 903 ms 77424 KB Output is correct
59 Correct 1 ms 2392 KB Output is correct
60 Correct 1 ms 2392 KB Output is correct
61 Correct 1 ms 2396 KB Output is correct
62 Correct 1260 ms 126908 KB Output is correct
63 Correct 1252 ms 126756 KB Output is correct
64 Correct 1239 ms 126088 KB Output is correct
65 Correct 10 ms 4188 KB Output is correct
66 Correct 22 ms 6204 KB Output is correct
67 Correct 527 ms 52724 KB Output is correct
68 Correct 983 ms 80340 KB Output is correct
69 Correct 1411 ms 106220 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 2480 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 512 ms 63708 KB Output is correct
10 Correct 18 ms 8232 KB Output is correct
11 Correct 128 ms 34088 KB Output is correct
12 Correct 29 ms 10928 KB Output is correct
13 Correct 98 ms 27708 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 4 ms 3420 KB Output is correct
16 Correct 487 ms 63496 KB Output is correct
17 Correct 1124 ms 126756 KB Output is correct
18 Correct 1157 ms 125872 KB Output is correct
19 Correct 1098 ms 94420 KB Output is correct
20 Correct 1584 ms 115848 KB Output is correct
21 Correct 1214 ms 110116 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 134 ms 17984 KB Output is correct
24 Correct 77 ms 12616 KB Output is correct
25 Correct 414 ms 38744 KB Output is correct
26 Correct 815 ms 65596 KB Output is correct
27 Correct 673 ms 57088 KB Output is correct
28 Correct 911 ms 72408 KB Output is correct
29 Correct 1174 ms 85792 KB Output is correct
30 Correct 1559 ms 98856 KB Output is correct
31 Correct 1948 ms 112112 KB Output is correct
32 Correct 1662 ms 122452 KB Output is correct
33 Correct 1272 ms 126756 KB Output is correct
34 Correct 14 ms 4956 KB Output is correct
35 Correct 27 ms 7032 KB Output is correct
36 Correct 609 ms 56240 KB Output is correct
37 Correct 1059 ms 85900 KB Output is correct
38 Correct 1600 ms 113756 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 2480 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 512 ms 63708 KB Output is correct
10 Correct 18 ms 8232 KB Output is correct
11 Correct 128 ms 34088 KB Output is correct
12 Correct 29 ms 10928 KB Output is correct
13 Correct 98 ms 27708 KB Output is correct
14 Correct 2 ms 2904 KB Output is correct
15 Correct 4 ms 3420 KB Output is correct
16 Correct 487 ms 63496 KB Output is correct
17 Correct 0 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 0 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 2032 ms 140596 KB Output is correct
24 Correct 1 ms 2396 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 4776 KB Output is correct
28 Correct 626 ms 51288 KB Output is correct
29 Correct 993 ms 80168 KB Output is correct
30 Correct 1480 ms 106788 KB Output is correct
31 Correct 2255 ms 140224 KB Output is correct
32 Correct 0 ms 2484 KB Output is correct
33 Correct 0 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 0 ms 2396 KB Output is correct
37 Correct 1 ms 2396 KB Output is correct
38 Correct 1 ms 2396 KB Output is correct
39 Correct 0 ms 2396 KB Output is correct
40 Correct 0 ms 2396 KB Output is correct
41 Correct 0 ms 2396 KB Output is correct
42 Correct 1 ms 2396 KB Output is correct
43 Correct 4 ms 3420 KB Output is correct
44 Correct 7 ms 3676 KB Output is correct
45 Correct 533 ms 52052 KB Output is correct
46 Correct 906 ms 77392 KB Output is correct
47 Correct 982 ms 77352 KB Output is correct
48 Correct 0 ms 2396 KB Output is correct
49 Correct 0 ms 2492 KB Output is correct
50 Correct 0 ms 2396 KB Output is correct
51 Correct 1 ms 2392 KB Output is correct
52 Correct 0 ms 2396 KB Output is correct
53 Correct 0 ms 2396 KB Output is correct
54 Correct 0 ms 2396 KB Output is correct
55 Incorrect 2509 ms 132192 KB Tree @(5, 130541) appears more than once: for edges on positions 149015 and 166682
56 Halted 0 ms 0 KB -