oj.uz

Submission #827171

# Submission time Handle Problem Language Result Execution time Memory
827171 2023-08-16T09:36:35 Z Sohsoh84 Fountain Parks (IOI21_parks) C++17
0 / 100
 158 ms 21472 KB 
#include "parks.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pll;

#define all(x)		(x).begin(), (x).end()
#define X		first
#define Y		second
#define sep		' '
#define debug(x)	cerr << #x << ": " << x << endl;

const int MAXN = 1e6 + 10;
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};

namespace answer {
	vector<int> u, v, a, b;
}

vector<pair<pll, int>> edges;

int X[MAXN], Y[MAXN], par[MAXN], n;
map<pll, int> mp;

int find(int v) {
	return par[v] == v ? v : par[v] = find(par[v]);
}

inline bool unite(int u_, int v_) {
	int u = find(u_), v = find(v_);
	if (u == v) return false;

	edges.push_back({{u_, v_}, (int)answer::u.size()});

	answer::u.push_back(u_);
	answer::v.push_back(v_);
	par[u] = v;

	return true;
}

int construct_roads(vector<int> x_, vector<int> y_) {
	n = x_.size();
	for (int i = 0; i < n; i++) {
		X[i] = x_[i];
		Y[i] = y_[i];

		mp[pll(X[i], Y[i])] = i;
		par[i] = i;
	}

	int edg = 0;
	for (int i = 0; i < 4; i++) {
		for (int v = 0; v < n; v++) {
			int ux = X[v] + 2 * DX[i], uy = Y[v] + 2 * DY[i];
			auto it = mp.find(pll(ux, uy));
			if (it == mp.end()) continue;

			int u = it -> second;	
			edg += unite(u, v);
		}
	}

	if (edg < n - 1) return 0;

	sort(all(edges), [] (const pair<pll, int>& a, const pair<pll, int>& b) {
		return min(X[a.X.X], X[a.X.Y]) < min(X[b.X.X], X[b.X.Y]);
	});

	set<pll> st;
	for (int ti = 0; ti < n - 1; ti++) {
		int i = edges[ti].Y;

		if (X[answer::u[i]] == X[answer::v[i]]) {
			int tx = X[answer::u[i]] - 1, ty = (Y[answer::u[i]] + Y[answer::v[i]]) / 2;	
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			tx += 2;
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			return 0;
		} else {
			int ty = Y[answer::u[i]] - 1, tx = (X[answer::u[i]] + X[answer::v[i]]) / 2;	
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			ty += 2;
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a.push_back(tx);
				answer::b.push_back(ty);
				continue;
			}

			return 0;
		}
	}

	build(answer::u, answer::v, answer::a, answer::b);
	return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 158 ms 21472 KB Tree (a[0], b[0]) = (1, 107217) is not adjacent to edge between u[0]=30345 @(2, 15658) and v[0]=0 @(2, 15660)
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 158 ms 21472 KB Tree (a[0], b[0]) = (1, 107217) is not adjacent to edge between u[0]=30345 @(2, 15658) and v[0]=0 @(2, 15660)
10 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 158 ms 21472 KB Tree (a[0], b[0]) = (1, 107217) is not adjacent to edge between u[0]=30345 @(2, 15658) and v[0]=0 @(2, 15660)
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 158 ms 21472 KB Tree (a[0], b[0]) = (1, 107217) is not adjacent to edge between u[0]=30345 @(2, 15658) and v[0]=0 @(2, 15660)
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 158 ms 21472 KB Tree (a[0], b[0]) = (1, 107217) is not adjacent to edge between u[0]=30345 @(2, 15658) and v[0]=0 @(2, 15660)
10 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Incorrect 158 ms 21472 KB Tree (a[0], b[0]) = (1, 107217) is not adjacent to edge between u[0]=30345 @(2, 15658) and v[0]=0 @(2, 15660)
10 Halted 0 ms 0 KB -