Submission #619744

#	Time	Username	Problem	Language	Result	Execution time	Memory
619744		amunduzbaev	Fountain Parks (IOI21_parks)	C++17	45 / 100	1004 ms	62716 KiB

parks

#include "parks.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

#define ar array
#define sow cerr<<"start"<<endl;
#define wow cerr<<"end"<<endl;
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)){
				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)){
				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);
	//~ cout<<m<<endl;
	function<void(int)> dfs = [&](int i){
		assert(!used[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;
		//~ sow
		p[i] = x;
		dfs(i);
		//~ wow
	}
	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: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30