답안 #772895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772895	2023-07-04T12:29:01 Z	numberes	분수 공원 (IOI21_parks)	C++17	5 / 100	263 ms	55076 KB

parks

/**
 * @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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #772895

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0