Submission #1044579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044579		Unforgettablepl	Fountain Parks (IOI21_parks)	C++17	15 / 100	584 ms	75940 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;
	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++){
		if(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[{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[{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[{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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30