oj.uz

Submission #827199

# Submission time Handle Problem Language Result Execution time Memory
827199 2023-08-16T09:50:36 Z Sohsoh84 Fountain Parks (IOI21_parks) C++17
5 / 100
 1299 ms 45740 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 v = 0; v < n; v++) {

		for (int i = 0; i < 4; i++) {
			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] + Y[a.X.X], X[a.X.Y] + Y[a.X.Y]) < min(X[b.X.X] + Y[b.X.X], X[a.X.Y] + Y[a.X.Y]);
			});

	set<pll> st;
	answer::a.resize(n - 1);
	answer::b.resize(n - 1);

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

		cerr  << answer::u[i] << sep << answer::v[i] << endl;
		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[i] = tx;	
				answer::b[i] = ty;	
				continue;
			}

			tx += 2;
			if (st.find(pll(tx, ty)) == st.end()) {
				st.insert(pll(tx, ty));
				answer::a[i] = tx;	
				answer::b[i] = 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[i] = tx;	
				answer::b[i] = ty;	
				continue;
			}

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

			return 0;
		}
	}

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 558 ms 22824 KB Output is correct
10 Correct 48 ms 2560 KB Output is correct
11 Correct 268 ms 12412 KB Output is correct
12 Correct 89 ms 3724 KB Output is correct
13 Correct 26 ms 5676 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 556 ms 22824 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 558 ms 22824 KB Output is correct
10 Correct 48 ms 2560 KB Output is correct
11 Correct 268 ms 12412 KB Output is correct
12 Correct 89 ms 3724 KB Output is correct
13 Correct 26 ms 5676 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 556 ms 22824 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 359 ms 24912 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 558 ms 22824 KB Output is correct
10 Correct 48 ms 2560 KB Output is correct
11 Correct 268 ms 12412 KB Output is correct
12 Correct 89 ms 3724 KB Output is correct
13 Correct 26 ms 5676 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 556 ms 22824 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 359 ms 24912 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 558 ms 22824 KB Output is correct
10 Correct 48 ms 2560 KB Output is correct
11 Correct 268 ms 12412 KB Output is correct
12 Correct 89 ms 3724 KB Output is correct
13 Correct 26 ms 5676 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 556 ms 22824 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Incorrect 304 ms 24864 KB Solution announced impossible, but it is possible.
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 558 ms 22824 KB Output is correct
10 Correct 48 ms 2560 KB Output is correct
11 Correct 268 ms 12412 KB Output is correct
12 Correct 89 ms 3724 KB Output is correct
13 Correct 26 ms 5676 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 556 ms 22824 KB Output is correct
17 Correct 1299 ms 45740 KB Output is correct
18 Incorrect 1054 ms 34092 KB Solution announced impossible, but it is possible.
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 558 ms 22824 KB Output is correct
10 Correct 48 ms 2560 KB Output is correct
11 Correct 268 ms 12412 KB Output is correct
12 Correct 89 ms 3724 KB Output is correct
13 Correct 26 ms 5676 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 556 ms 22824 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 312 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Incorrect 359 ms 24912 KB Solution announced impossible, but it is possible.
24 Halted 0 ms 0 KB -