Submission #1044591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044591		Unforgettablepl	Fountain Parks (IOI21_parks)	C++17	5 / 100	538 ms	54692 KiB

parks

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

int construct_roads(vector<int> x,vector<int> y){
	int n = x.size();
	map<pair<int,int>,int> lookup;
	set<pair<int,int>> edges;
	for(int i=0;i<n;i++)lookup[{x[i],y[i]}]=i;
	vector<int> u,v,a,b;
	vector<vector<int>> adj(n);
	for(int i=0;i<n;i++){
		bool works = false;
		if(lookup.count({x[i]+2,y[i]})){
			works=true;
			if(edges.count({i,lookup[{x[i]+2,y[i]}]}))continue;
			edges.emplace(lookup[{x[i]+2,y[i]}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i]+2,y[i]}]);
			adj[i].emplace_back(lookup[{x[i]+2,y[i]}]);
			adj[lookup[{x[i]+2,y[i]}]].emplace_back(i);
			a.emplace_back(x[i]+1);
			b.emplace_back(y[i]-1);
		}
		if(lookup.count({x[i]-2,y[i]})){
			works = true;
			if(edges.count({i,lookup[{x[i]-2,y[i]}]}))continue;
			edges.emplace(lookup[{x[i]-2,y[i]}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i]-2,y[i]}]);
			adj[i].emplace_back(lookup[{x[i]-2,y[i]}]);
			adj[lookup[{x[i]-2,y[i]}]].emplace_back(i);
			a.emplace_back(x[i]-1);
			b.emplace_back(y[i]-1);
		}
		if(x[i]==4 and works)continue;
		if(lookup.count({x[i],y[i]+2})){
			if(edges.count({i,lookup[{x[i],y[i]+2}]}))continue;
			edges.emplace(lookup[{x[i],y[i]+2}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i],y[i]+2}]);
			adj[i].emplace_back(lookup[{x[i],y[i]+2}]);
			adj[lookup[{x[i],y[i]+2}]].emplace_back(i);
			if(x[i]==2)a.emplace_back(x[i]-1);
			else a.emplace_back(x[i]+1);
			b.emplace_back(y[i]+1);
		}
		if(lookup.count({x[i],y[i]-2})){
			if(edges.count({i,lookup[{x[i],y[i]-2}]}))continue;
			edges.emplace(lookup[{x[i],y[i]-2}],i);
			u.emplace_back(i);
			v.emplace_back(lookup[{x[i],y[i]-2}]);
			adj[i].emplace_back(lookup[{x[i],y[i]-2}]);
			adj[lookup[{x[i],y[i]-2}]].emplace_back(i);
			if(x[i]==2)a.emplace_back(x[i]-1);
			else a.emplace_back(x[i]+1);
			b.emplace_back(y[i]-1);
		}
	}
	vector<bool> visited(n);
	int vis = 0;
	function<void(int)> dfs = [&](int x){
		if(visited[x])return;
		visited[x]=true;
		vis++;
		for(int&i:adj[x])dfs(i);
	};
	dfs(0);
	if(vis!=n)return 0;
	build(u,v,a,b);
	return 1;
}

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