oj.uz

Submission #773470

# Submission time Handle Problem Language Result Execution time Memory
773470 2023-07-05T05:49:52 Z SanguineChameleon Fountain Parks (IOI21_parks) C++17
0 / 100
 8 ms 14292 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
vector<int> adj[maxn * 3];
bool flag[maxn * 3];
map<pair<int, int>, int> even_id;
map<pair<int, int>, int> odd_id;
vector<pair<int, int>> odds;
vector<pair<int, int>> roads;
int node_cnt;
int road_cnt;
vector<int> path;

int get_even_id(int x, int y) {
	auto it = even_id.find(make_pair(x, y));
	if (it == even_id.end()) {
		return -1;
	}
	else {
		return it->second;
	}
}

int get_odd_id(int x, int y) {
	auto it = odd_id.find(make_pair(x, y));
	if (it != odd_id.end()) {
		return it->second;
	}
	else {
		odds.emplace_back(x, y);
		return odd_id[make_pair(x, y)] = node_cnt++;
	}
}

void add_edge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
}

void dfs(int u) {
	flag[u] = true;
	path.push_back(u);
	for (auto v: adj[u]) {
		if (!flag[v]) {
			dfs(v);
		}
	}
}

int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	for (int i = 0; i < n; i++) {
		even_id[make_pair(x[i], y[i])] = i;
	}
	for (int u = 0; u < n; u++) {
		int v = get_even_id(x[u] + 2, y[u]);
		if (v != -1) {
			roads.emplace_back(u, v);
			add_edge(u, v);
		}
		v = get_even_id(x[u], y[u] + 2);
		if (v != -1) {
			roads.emplace_back(u, v);
			add_edge(u, v);
		}
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		if (!flag[i]) {
			return 0;
		}
	}
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}
	bool sub2 = true;
	for (int i = 0; i < n; i++) {
		sub2 &= x[i] <= 4;
	}
	road_cnt = roads.size();
	node_cnt = road_cnt;
	if (sub2) {
		vector<int> _u, _v, a, b;
		for (int i = 0; i < road_cnt; i++) {
			int u = roads[i].first;
			int v = roads[i].second;
			_u.push_back(u);
			_v.push_back(v);
			if (y[u] == y[v]) {
				a.push_back(x[u] + 1);
				b.push_back(y[v] + 1);
			}
			else if (x[u] == 2) {
				a.push_back(x[u] - 1);
				b.push_back(y[v] + 1);
			}
			else {
				a.push_back(x[u] + 1);
				b.push_back(y[v] + 1);
			}
		}
		build(_u, _v, a, b);
		return 1;
	}
	for (int i = 0; i < road_cnt; i++) {
		int u = roads[i].first;
		int v = roads[i].second;
		if (y[u] == y[v]) {
			add_edge(i, get_odd_id(x[u] + 1, y[u] - 1));
			add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
		}
		else {
			add_edge(i, get_odd_id(x[u] - 1, y[u] + 1));
			add_edge(i, get_odd_id(x[u] + 1, y[u] + 1));
		}
	}
	vector<int> u, v, a, b;
	for (int i = 0; i < node_cnt; i++) {
		flag[i] = false;
	}
	for (int iter = 0; iter < 2; iter++) {
		for (int i = road_cnt; i < node_cnt; i++) {
			if (!flag[i] && (iter == 1 || (int)adj[i].size() == 1)) {
				path.clear();
				dfs(i);
				for (int j = 0; j + 1 < (int)path.size(); j += 2) {
					u.push_back(roads[path[j + 1]].first);
					v.push_back(roads[path[j + 1]].second);
					a.push_back(odds[path[j] - road_cnt].first);
					b.push_back(odds[path[j] - road_cnt].second);
				}
			}
		}
	}
	build(u, v, a, b);
	return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 8 ms 14292 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 8 ms 14292 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 8 ms 14292 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 8 ms 14292 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 8 ms 14292 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Incorrect 8 ms 14292 KB Tree (a[0], b[0]) = (1, 5) is not adjacent to edge between u[0]=0 @(2, 2) and v[0]=1 @(2, 4)
3 Halted 0 ms 0 KB -