Submission #616097

#	Time	Username	Problem	Language	Result	Execution time	Memory
616097		sofapuden	Fountain Parks (IOI21_parks)	C++17	0 / 100	0 ms	212 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

vector<int> p;
vector<pair<int,int>> v;
set<pair<int,int>> ben;
map<pair<int,int>,int> M;

vector<int> U, V, A, B;

int u(int x){return p[x] == x ? x : p[x] = u(p[x]);}

void b(int x, int y){
	if(u(x) == u(y))return;
	if(v[x] > v[y])swap(x,y);
	if(v[x].first == v[y].first){
		if((v[x].second+v[x].first)%4 == 2){
			if(ben.count({v[x].second+1,v[x].first-1}))return;
			ben.insert({v[x].second+1,v[x].first-1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first-1);
			B.push_back(v[x].second+1);
			p[u(x)] = u(y);
		} else {
			if(ben.count({v[x].second+1,v[x].first+1}))return;
			ben.insert({v[x].second+1,v[x].first+1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first+1);
			B.push_back(v[x].second+1);
			p[u(x)] = u(y);
		}
	} else {
		if((v[x].second+v[x].first)%4 == 2){
			if(ben.count({v[x].second+1,v[x].first+1}))return;
			ben.insert({v[x].second+1,v[x].first+1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first+1);
			B.push_back(v[x].second+1);
			p[u(x)] = u(y);
		} else {
			if(ben.count({v[x].second-1,v[x].first+1}))return;
			ben.insert({v[x].second-1,v[x].first+1});
			U.push_back(M[v[x]]);
			V.push_back(M[v[y]]);
			A.push_back(v[x].first+1);
			B.push_back(v[x].second-1);
			p[u(x)] = u(y);
		}
	}
}

int construct_roads(vector<int> x, vector<int> y) {	
	int n = x.size();
	p.resize(n);
	iota(p.begin(),p.end(),0);
	for(int i = 0; i < n; ++i){v.emplace_back(x[i],y[i]);M[v.back()]=i;}
	map<pair<int,int>,int> S;
	sort(v.begin(),v.end());
	for(int i = 0; i < n; ++i){
		if(S[{v[i].first-2,v[i].second}])b(i,S[{v[i].first-2,v[i].second}]-1);
		if(S[{v[i].first,v[i].second-2}])b(i,S[{v[i].first,v[i].second-2}]-1);
		S[{v[i].first,v[i].second}] = i+1;
	}
	build(U,V,A,B);
	return 1;
}

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