oj.uz

Submission #617807

# Submission time Handle Problem Language Result Execution time Memory
617807 2022-08-01T14:42:43 Z amunduzbaev Fountain Parks (IOI21_parks) C++17
5 / 100
 841 ms 49816 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -