oj.uz

Submission #772895

# Submission time Handle Problem Language Result Execution time Memory
772895 2023-07-04T12:29:01 Z numberes Fountain Parks (IOI21_parks) C++17
5 / 100
 263 ms 55076 KB 
/**
 * @date    2023-07-04 19:59:53
 * RAmen!
 */
#include "parks.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define ll long long
using namespace std;
vector<int> U, V, A, B;
map<int, int> c[200005], used[200005];
pii p[200005];
int n, fa[200005];
// B for horizontal edges; W for vertical edges
int fnd(int x) {
	return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}
void add_edge(int u, int v, int a, int b) {
	U.pb(u - 1); V.pb(v - 1); A.pb(a); B.pb(b); used[a][b] = 1;
}
int construct_roads(vector<int> x, vector<int> y) {
	n = (int)x.size();
	for(int i = 0; i < n; i++) {
		c[x[i]][y[i]] = i + 1; fa[i + 1] = i + 1;
		p[i + 1] = mp(x[i], y[i]);
	}
	sort(p + 1, p + n + 1, [&](pii a, pii b){return mp(a.se, a.fi) < mp(b.se, b.fi);});
	for(int l = 1, r; l <= n; l = r + 1) {
		r = l; while(p[r].se == p[l].se) r++; r--;
		for(int i = l; i <= r; i++) {
			int a = p[i].fi, b = p[i].se;
			if(!c[a].count(b - 2)) continue;
			if(fnd(c[a][b]) == fnd(c[a][b - 2])) continue;
			fa[c[a][b]] = c[a][b - 2];
			if((a + 1) % 4 == (b - 1) % 4) { // W
				add_edge(c[a][b - 2], c[a][b], a + 1, b - 1);
			}
			else if(!used[a - 1][b - 1]){ // B
				add_edge(c[a][b - 2], c[a][b], a - 1, b - 1);
			}
		}
		for(int i = l; i <= r; i++) {
			int a = p[i].fi, b = p[i].se;
			if(!c[a - 2].count(b)) continue;
			if(fnd(c[a][b]) == fnd(c[a - 2][b])) continue;
			fa[c[a][b]] = c[a - 2][b];
			if((a - 1) % 4 != (b + 1) % 4) { // B
				add_edge(c[a - 2][b], c[a][b], a - 1, b + 1);
			}
			else if(!used[a - 1][b - 1]){ // B
				add_edge(c[a - 2][b], c[a][b], a - 1, b - 1);
			}
		}
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++) cnt += (fa[i] == i);
	if(cnt > 1) return 0;
	build(U, V, A, B);
	return 1;
}
/*
.-.
  |
.-.
|
.-.
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19092 KB Output is correct
5 Correct 10 ms 19016 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 11 ms 19096 KB Output is correct
9 Correct 142 ms 36668 KB Output is correct
10 Correct 21 ms 21052 KB Output is correct
11 Correct 74 ms 28540 KB Output is correct
12 Correct 31 ms 21928 KB Output is correct
13 Correct 50 ms 25492 KB Output is correct
14 Correct 11 ms 19156 KB Output is correct
15 Correct 11 ms 19360 KB Output is correct
16 Correct 150 ms 36732 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19092 KB Output is correct
5 Correct 10 ms 19016 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 11 ms 19096 KB Output is correct
9 Correct 142 ms 36668 KB Output is correct
10 Correct 21 ms 21052 KB Output is correct
11 Correct 74 ms 28540 KB Output is correct
12 Correct 31 ms 21928 KB Output is correct
13 Correct 50 ms 25492 KB Output is correct
14 Correct 11 ms 19156 KB Output is correct
15 Correct 11 ms 19360 KB Output is correct
16 Correct 150 ms 36732 KB Output is correct
17 Incorrect 10 ms 19028 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19092 KB Output is correct
5 Correct 10 ms 19016 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 11 ms 19096 KB Output is correct
9 Correct 142 ms 36668 KB Output is correct
10 Correct 21 ms 21052 KB Output is correct
11 Correct 74 ms 28540 KB Output is correct
12 Correct 31 ms 21928 KB Output is correct
13 Correct 50 ms 25492 KB Output is correct
14 Correct 11 ms 19156 KB Output is correct
15 Correct 11 ms 19360 KB Output is correct
16 Correct 150 ms 36732 KB Output is correct
17 Incorrect 10 ms 19028 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19092 KB Output is correct
5 Correct 10 ms 19016 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 11 ms 19096 KB Output is correct
9 Correct 142 ms 36668 KB Output is correct
10 Correct 21 ms 21052 KB Output is correct
11 Correct 74 ms 28540 KB Output is correct
12 Correct 31 ms 21928 KB Output is correct
13 Correct 50 ms 25492 KB Output is correct
14 Correct 11 ms 19156 KB Output is correct
15 Correct 11 ms 19360 KB Output is correct
16 Correct 150 ms 36732 KB Output is correct
17 Correct 13 ms 19096 KB Output is correct
18 Incorrect 9 ms 19028 KB Solution announced impossible, but it is possible.
19 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19092 KB Output is correct
5 Correct 10 ms 19016 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 11 ms 19096 KB Output is correct
9 Correct 142 ms 36668 KB Output is correct
10 Correct 21 ms 21052 KB Output is correct
11 Correct 74 ms 28540 KB Output is correct
12 Correct 31 ms 21928 KB Output is correct
13 Correct 50 ms 25492 KB Output is correct
14 Correct 11 ms 19156 KB Output is correct
15 Correct 11 ms 19360 KB Output is correct
16 Correct 150 ms 36732 KB Output is correct
17 Correct 263 ms 54808 KB Output is correct
18 Correct 256 ms 55076 KB Output is correct
19 Incorrect 143 ms 48772 KB Solution announced impossible, but it is possible.
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 10 ms 19068 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 9 ms 19092 KB Output is correct
5 Correct 10 ms 19016 KB Output is correct
6 Correct 10 ms 19028 KB Output is correct
7 Correct 9 ms 19028 KB Output is correct
8 Correct 11 ms 19096 KB Output is correct
9 Correct 142 ms 36668 KB Output is correct
10 Correct 21 ms 21052 KB Output is correct
11 Correct 74 ms 28540 KB Output is correct
12 Correct 31 ms 21928 KB Output is correct
13 Correct 50 ms 25492 KB Output is correct
14 Correct 11 ms 19156 KB Output is correct
15 Correct 11 ms 19360 KB Output is correct
16 Correct 150 ms 36732 KB Output is correct
17 Incorrect 10 ms 19028 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -