oj.uz

Submission #617805

# Submission time Handle Problem Language Result Execution time Memory
617805 2022-08-01T14:40:15 Z amunduzbaev Fountain Parks (IOI21_parks) C++17
5 / 100
 845 ms 52248 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();
	
	//~ 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

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

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

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

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

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

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