oj.uz

Submission #435564

# Submission time Handle Problem Language Result Execution time Memory
435564 2021-06-23T12:39:33 Z grt Fountain Parks (IOI21_parks) C++17
5 / 100
 540 ms 155908 KB 
#include <bits/stdc++.h>
#include "parks.h"
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 400 * 1000 + 10;
map<pi, int>fontain;
pi road[nax];
int n;
vi V[nax], V2[nax];
map<pi, int>pts;
pi inv[nax];
bool vis[nax];
int match[nax];

bool augument(int u) {
	vis[u] = true;
	for(int v : V[u]) {
		if(match[v] == -1) {
			match[u] = v;
			match[v] = u;
			return true;
		}
	}
	for(int v : V[u]) {
		if(!vis[match[v]] && augument(match[v])) {
			match[u] = v;
			match[v] = u;
			return true;
		}
	}
	return false;
}

void dfs(int x) {
	vis[x] = true;
	for(int nbh : V2[x]) if(!vis[nbh]) {
		dfs(nbh);
	}
}

int construct_roads(vi xx, vi yx) {
	for(int i = 0; i < (int)xx.size(); ++i) {
		fontain[{xx[i], yx[i]}] = i;
	}
	for(auto it : fontain) {
		auto [x, y] = it.ST;
		if(fontain.count({x + 2, y})) {
			road[n] = {it.ND, fontain[{x + 2, y}]};
			pts[{x + 1, y - 1}];
			pts[{x + 1, y + 1}];
			n++;
		}
		if(fontain.count({x, y + 2})) {
			road[n] = {it.ND, fontain[{x, y + 2}]};
			pts[{x - 1, y + 1}];
			pts[{x + 1, y + 1}];
			n++;
		}
	}
	int id = 0;
	for(auto &it : pts) {
		inv[id] = it.ST;
		it.ND = id++;
	}
	for(int i = 0; i < n; ++i) {
		V2[road[i].ST].PB(road[i].ND);
		V2[road[i].ND].PB(road[i].ST);
		int x1 = xx[road[i].ST], y1 = yx[road[i].ST];
		int x2 = xx[road[i].ND], y2 = yx[road[i].ND];
		if(x1 == x2) {
			int y = (y1 + y2) / 2;
			for(int x : {x1 - 1, x1 + 1}) {
				int nr = pts[{x, y}];
				V[i].emplace_back(n + nr);
				V[n + nr].emplace_back(i);
			}
		} else if(y1 == y2) {
			int x = (x1 + x2) / 2;
			for(int y : {y1 - 1, y1 + 1}) {
				int nr = pts[{x, y}];
				V[i].emplace_back(n + nr);
				V[n + nr].emplace_back(i);
			}
		}
	}
	dfs(0);
	for(int i = 0; i < (int)xx.size(); ++i) {
		if(!vis[i]) {
			return 0;
		}
	}
	for(int i = 0; i < n + id; ++i) {
		match[i] = -1;
	}
	while(true) {
		bool any = false;
		for(int i = 0; i < n + id; ++i) {
			vis[i] = false;
		}
		for(int i = 0; i < n + id; ++i) {
			if(match[i] == -1 && augument(i)) {
				any = true;
			}
		}
		if(!any) break;
	}
	for(int i = 0; i < n; ++i) {
		if(match[i] == -1) {
			return 0;
		}
	}
	vi u(n), v(n), a(n), b(n);
	for(int i = 0; i < n; ++i) {
		u[i] = road[i].ST;
		v[i] = road[i].ND;
		a[i] = inv[match[i]].ST;
		b[i] = inv[match[i]].ND;
	}
	build(u,v,a,b);
	return 1;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
//}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 12 ms 19092 KB Output is correct
4 Correct 12 ms 19056 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 12 ms 19020 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 12 ms 19020 KB Output is correct
9 Correct 312 ms 62028 KB Output is correct
10 Correct 34 ms 23492 KB Output is correct
11 Correct 151 ms 42320 KB Output is correct
12 Correct 46 ms 25728 KB Output is correct
13 Correct 109 ms 35228 KB Output is correct
14 Correct 13 ms 19404 KB Output is correct
15 Correct 16 ms 19788 KB Output is correct
16 Correct 324 ms 61328 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 12 ms 19092 KB Output is correct
4 Correct 12 ms 19056 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 12 ms 19020 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 12 ms 19020 KB Output is correct
9 Correct 312 ms 62028 KB Output is correct
10 Correct 34 ms 23492 KB Output is correct
11 Correct 151 ms 42320 KB Output is correct
12 Correct 46 ms 25728 KB Output is correct
13 Correct 109 ms 35228 KB Output is correct
14 Correct 13 ms 19404 KB Output is correct
15 Correct 16 ms 19788 KB Output is correct
16 Correct 324 ms 61328 KB Output is correct
17 Incorrect 12 ms 19136 KB a[0] = 0 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 12 ms 19092 KB Output is correct
4 Correct 12 ms 19056 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 12 ms 19020 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 12 ms 19020 KB Output is correct
9 Correct 312 ms 62028 KB Output is correct
10 Correct 34 ms 23492 KB Output is correct
11 Correct 151 ms 42320 KB Output is correct
12 Correct 46 ms 25728 KB Output is correct
13 Correct 109 ms 35228 KB Output is correct
14 Correct 13 ms 19404 KB Output is correct
15 Correct 16 ms 19788 KB Output is correct
16 Correct 324 ms 61328 KB Output is correct
17 Incorrect 12 ms 19136 KB a[0] = 0 is not an odd integer
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 12 ms 19092 KB Output is correct
4 Correct 12 ms 19056 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 12 ms 19020 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 12 ms 19020 KB Output is correct
9 Correct 312 ms 62028 KB Output is correct
10 Correct 34 ms 23492 KB Output is correct
11 Correct 151 ms 42320 KB Output is correct
12 Correct 46 ms 25728 KB Output is correct
13 Correct 109 ms 35228 KB Output is correct
14 Correct 13 ms 19404 KB Output is correct
15 Correct 16 ms 19788 KB Output is correct
16 Correct 324 ms 61328 KB Output is correct
17 Incorrect 13 ms 19084 KB Tree (a[0], b[0]) = (200001, 3) is not adjacent to edge between u[0]=2 @(199998, 2) and v[0]=0 @(200000, 2)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 12 ms 19092 KB Output is correct
4 Correct 12 ms 19056 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 12 ms 19020 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 12 ms 19020 KB Output is correct
9 Correct 312 ms 62028 KB Output is correct
10 Correct 34 ms 23492 KB Output is correct
11 Correct 151 ms 42320 KB Output is correct
12 Correct 46 ms 25728 KB Output is correct
13 Correct 109 ms 35228 KB Output is correct
14 Correct 13 ms 19404 KB Output is correct
15 Correct 16 ms 19788 KB Output is correct
16 Correct 324 ms 61328 KB Output is correct
17 Runtime error 540 ms 155908 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 12 ms 19092 KB Output is correct
4 Correct 12 ms 19056 KB Output is correct
5 Correct 12 ms 19020 KB Output is correct
6 Correct 12 ms 19020 KB Output is correct
7 Correct 11 ms 19024 KB Output is correct
8 Correct 12 ms 19020 KB Output is correct
9 Correct 312 ms 62028 KB Output is correct
10 Correct 34 ms 23492 KB Output is correct
11 Correct 151 ms 42320 KB Output is correct
12 Correct 46 ms 25728 KB Output is correct
13 Correct 109 ms 35228 KB Output is correct
14 Correct 13 ms 19404 KB Output is correct
15 Correct 16 ms 19788 KB Output is correct
16 Correct 324 ms 61328 KB Output is correct
17 Incorrect 12 ms 19136 KB a[0] = 0 is not an odd integer
18 Halted 0 ms 0 KB -