oj.uz

Submission #617890

# Submission time Handle Problem Language Result Execution time Memory
617890 2022-08-01T16:25:23 Z amunduzbaev Fountain Parks (IOI21_parks) C++17
0 / 100
 9 ms 9992 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});
	};
	
	vector<int> par(n), sz(n, 1);
	iota(par.begin(), par.end(), 0);
	function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
	auto merge = [&](int a, int b){
		a = f(a), b = f(b);
		if(a == b) return false;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a, sz[a] += sz[b];
		return true;
	};
	
	for(int i=0;i<n;i++){
		if(ss.count({x[i] - 2, y[i]})){
			int j = ss[{x[i] - 2, y[i]}];
			if(!merge(i, j)) continue;
			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}];
			if(!merge(i, j)) continue;
			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(sz[f(0)] != n) {
		assert(false);
		return 0;
	}
	int m = e.size();
	
	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(auto [x, i] : mm){
		if(used[i]) continue;
		p[i] = x;
		dfs(i);
	}
	
	for(int i=0;i<m;i++){
		if(used[i]) continue;
		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];
	}
	
	build(u, v, A, B);
	return 1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Runtime error 9 ms 9992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Runtime error 9 ms 9992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Runtime error 9 ms 9992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Runtime error 9 ms 9992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Runtime error 9 ms 9992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Runtime error 9 ms 9992 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -