답안 #617805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
617805	2022-08-01T14:40:15 Z	amunduzbaev	분수 공원 (IOI21_parks)	C++17	5 / 100	845 ms	52248 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();
	
	//~ for(int i=0;i<m;i++){
		//~ cout<<e[i][0]<<" "<<e[i][1]<<"\n";
	//~ }
	//~ for(int i=0;i<m;i++){
		//~ cout<<i<<" : ";
		//~ for(auto x : edges[i]){
			//~ cout<<x[0]<<" ";
		//~ } cout<<"\n";
	//~ }

	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;
	}
	
	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	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	324 ms	31936 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	104 ms	19468 KB	Output is correct
12	Correct	29 ms	9072 KB	Output is correct
13	Correct	72 ms	14652 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	328 ms	31992 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	324 ms	31936 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	104 ms	19468 KB	Output is correct
12	Correct	29 ms	9072 KB	Output is correct
13	Correct	72 ms	14652 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	328 ms	31992 KB	Output is correct
17	Incorrect	3 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	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	324 ms	31936 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	104 ms	19468 KB	Output is correct
12	Correct	29 ms	9072 KB	Output is correct
13	Correct	72 ms	14652 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	328 ms	31992 KB	Output is correct
17	Incorrect	3 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	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	324 ms	31936 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	104 ms	19468 KB	Output is correct
12	Correct	29 ms	9072 KB	Output is correct
13	Correct	72 ms	14652 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	328 ms	31992 KB	Output is correct
17	Correct	3 ms	4948 KB	Output is correct
18	Correct	3 ms	5000 KB	Output is correct
19	Correct	3 ms	5000 KB	Output is correct
20	Correct	710 ms	52248 KB	Output is correct
21	Incorrect	845 ms	49280 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	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	324 ms	31936 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	104 ms	19468 KB	Output is correct
12	Correct	29 ms	9072 KB	Output is correct
13	Correct	72 ms	14652 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	328 ms	31992 KB	Output is correct
17	Incorrect	691 ms	48864 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4992 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	2 ms	4948 KB	Output is correct
6	Correct	3 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	2 ms	4948 KB	Output is correct
9	Correct	324 ms	31936 KB	Output is correct
10	Correct	18 ms	7636 KB	Output is correct
11	Correct	104 ms	19468 KB	Output is correct
12	Correct	29 ms	9072 KB	Output is correct
13	Correct	72 ms	14652 KB	Output is correct
14	Correct	4 ms	5204 KB	Output is correct
15	Correct	5 ms	5332 KB	Output is correct
16	Correct	328 ms	31992 KB	Output is correct
17	Incorrect	3 ms	4948 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

답안 #617805

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