답안 #617807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
617807	2022-08-01T14:42:43 Z	amunduzbaev	분수 공원 (IOI21_parks)	C++17	5 / 100	841 ms	49816 KB

parks

#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});
	};
	
	for(int i=0;i<n;i++){
		if(ss.count({x[i] - 2, y[i]})){
			int j = ss[{x[i] - 2, y[i]}];
			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}];
			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;
			}
		}
	}
	
	int m = e.size();
	if(m != n - 1) return 0;
	assert(m == n - 1);
	for(int i=0;i<m;i++){
		assert((int)edges[i].size() <= 2);
	}
	
	for(auto [x, i] : mm){
		p[i] = x;
		assert((int)edges[i].size() < 2);
	}
	
	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(int i=0;i<m;i++){
		if(used[i]) continue;
		if(p[i][0] == -1){
			assert(edges[i].size() == 2);
			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];
		assert(~A[i] && ~B[i]);
	}
	
	build(u, v, A, B);
	return 1;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	4 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	347 ms	31908 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	112 ms	19632 KB	Output is correct
12	Correct	28 ms	9028 KB	Output is correct
13	Correct	68 ms	14608 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	318 ms	32004 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	4 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	347 ms	31908 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	112 ms	19632 KB	Output is correct
12	Correct	28 ms	9028 KB	Output is correct
13	Correct	68 ms	14608 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	318 ms	32004 KB	Output is correct
17	Incorrect	4 ms	4948 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	4 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	347 ms	31908 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	112 ms	19632 KB	Output is correct
12	Correct	28 ms	9028 KB	Output is correct
13	Correct	68 ms	14608 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	318 ms	32004 KB	Output is correct
17	Incorrect	4 ms	4948 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	4 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	347 ms	31908 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	112 ms	19632 KB	Output is correct
12	Correct	28 ms	9028 KB	Output is correct
13	Correct	68 ms	14608 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	318 ms	32004 KB	Output is correct
17	Correct	3 ms	4948 KB	Output is correct
18	Correct	3 ms	4948 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	709 ms	49816 KB	Output is correct
21	Incorrect	841 ms	47028 KB	Tree @(82093, 82089) appears more than once: for edges on positions 14236 and 118204
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	4 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	347 ms	31908 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	112 ms	19632 KB	Output is correct
12	Correct	28 ms	9028 KB	Output is correct
13	Correct	68 ms	14608 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	318 ms	32004 KB	Output is correct
17	Incorrect	670 ms	48816 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 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	4 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	2 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	347 ms	31908 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	112 ms	19632 KB	Output is correct
12	Correct	28 ms	9028 KB	Output is correct
13	Correct	68 ms	14608 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	318 ms	32004 KB	Output is correct
17	Incorrect	4 ms	4948 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

답안 #617807

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