Submission #1053021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053021		fuad27	Fountain Parks (IOI21_parks)	C++17	100 / 100	714 ms	73908 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
	vector<int> e;
	int cc=0;
	dsu(int n) {
		e=vector<int>(n, -1);
		cc=n;
	}
	int get(int x) {
		if(e[x]<0)return x;
		return e[x]=get(e[x]);
	}
	bool unite(int x, int y) {
		x=get(x),y=get(y);
		if(x==y)return false;
		if(-e[x] < -e[y]){
			swap(x, y);
		}
		cc--;
		e[x]+=e[y];
		e[y] = x;
		return true;
	}
};
int construct_roads(vector<int> x, vector<int> y) {
	vector<pair<int,int>> bc;
	int n = x.size();
	dsu d(n);
	map<pair<int,int>, int> mp;
	for(int i = 0;i<n;i++) {
		mp[{x[i], y[i]}] = i;
		bc.push_back({x[i]-1, y[i]-1});
		bc.push_back({x[i]-1, y[i]+1});
		bc.push_back({x[i]+1, y[i]-1});
		bc.push_back({x[i]+1, y[i]+1});
	}
	vector<int> a, b, c, D;
	map<pair<int,int>, int> vis;
	for(auto [u,v]:bc) {
		if(vis[{u, v}])continue;
		vis[{u,v}]=1;
		if((u+v)%4 == 2) {
			if(mp.find(pair{u-1, v+1})!=mp.end() and mp.find(pair{u+1, v+1}) != mp.end() and d.unite(mp[{u-1, v+1}], mp[{u+1, v+1}])) {
				a.push_back(mp[{u-1, v+1}]);
				b.push_back(mp[{u+1, v+1}]);
				c.push_back(u);
				D.push_back(v);
			}
			else if(mp.find(pair{u-1, v-1})!=mp.end() and mp.find(pair{u+1, v-1}) != mp.end() and d.unite(mp[{u-1, v-1}], mp[{u+1, v-1}])) {
				a.push_back(mp[{u-1, v-1}]);
				b.push_back(mp[{u+1, v-1}]);
				c.push_back(u);
				D.push_back(v);
			}
		}
		else {
			if(mp.find(pair{u+1, v+1})!=mp.end() and mp.find(pair{u+1, v-1}) != mp.end() and d.unite(mp[{u+1, v+1}], mp[{u+1, v-1}])) {
				a.push_back(mp[{u+1, v+1}]);
				b.push_back(mp[{u+1, v-1}]);
				c.push_back(u);
				D.push_back(v);
			}
			else if(mp.find(pair{u-1, v-1})!=mp.end() and mp.find(pair{u-1, v+1}) != mp.end() and d.unite(mp[{u-1, v-1}], mp[{u-1, v+1}])) {
				a.push_back(mp[{u-1, v-1}]);
				b.push_back(mp[{u-1, v+1}]);
				c.push_back(u);
				D.push_back(v);
			}
		}
	}
	if(d.cc!=1)return false;
	build(a, b, c, D);
	return true;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30