Submission #894896

#	Time	Username	Problem	Language	Result	Execution time	Memory
894896		MuhammadSaram	Fountain Parks (IOI21_parks)	C++17	5 / 100	783 ms	59980 KiB

parks

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

const int M = 2e5;

set<int> nei[M];
bool vis[M];

void dfs(int u)
{
	vis[u]=true;
	for (int i:nei[u])
		if (!vis[i])
			dfs(i);
}

int construct_roads(vector<int> x, vector<int> y)
{
	int n=x.size();
	map<pair<int,int>,int> ind;
	for (int i=0;i<n;i++)
		ind[{x[i],y[i]}]=i;
	for (int i=0;i<n;i++)
		for (int j=-2;j<=2;j+=2)
			for (int k=-2;k<=2;k+=2)
			{
				if ((j==0)==(k==0))
					continue;
				if (ind.find({x[i]+j,y[i]+k})!=ind.end())
					nei[i].insert(ind[{x[i]+j,y[i]+k}]);
			}
	dfs(0);
	for (int i=0;i<n;i++)
		if (!vis[i])
			return 0;
	set<pair<int,int>> se;
	vector<int> u,v,a,b;
	for (int i=0;i<n;i++)
	{
		bool o=true;
		for (int j=-2;j<=2 and o;j+=2)
			for (int k=-2;k<=2 and o;k+=2)
			{
				if ((j==0)==(k==0))
					continue;
				if (ind.find({x[i]+j,y[i]+k})==ind.end())
					o=false;
			}
		if (o)
		{
			u.push_back(i),v.push_back(ind[{x[i],y[i]-2}]);
			a.push_back(x[i]-1),b.push_back(y[i]-1);
			se.insert({a.back(),b.back()});
			u.push_back(i),v.push_back(ind[{x[i]-2,y[i]}]);
			a.push_back(x[i]-1),b.push_back(y[i]+1);
			se.insert({a.back(),b.back()});
			u.push_back(i),v.push_back(ind[{x[i],y[i]+2}]);
			a.push_back(x[i]+1),b.push_back(y[i]+1);
			se.insert({a.back(),b.back()});
			u.push_back(i),v.push_back(ind[{x[i]+2,y[i]}]);
			a.push_back(x[i]+1),b.push_back(y[i]-1);
			se.insert({a.back(),b.back()});
			nei[i].erase(ind[{x[i],y[i]-2}]),nei[ind[{x[i],y[i]-2}]].erase(i);
			nei[i].erase(ind[{x[i]-2,y[i]}]),nei[ind[{x[i]-2,y[i]}]].erase(i);
			nei[i].erase(ind[{x[i],y[i]+2}]),nei[ind[{x[i],y[i]+2}]].erase(i);
			nei[i].erase(ind[{x[i]+2,y[i]}]),nei[ind[{x[i]+2,y[i]}]].erase(i);
		}
	}
	for (int i=0;i<n;i++)
		for (int j:nei[i])
		{
			if (x[i]==x[j])
			{
				int avg=(y[i]+y[j])/2;
				if (se.find({x[i]-1,avg})==se.end())
				{
					u.push_back(i),v.push_back(j);
					a.push_back(x[i]-1),b.push_back(avg);
					se.insert({a.back(),b.back()});
				}
				else
				{
					u.push_back(i),v.push_back(j);
					a.push_back(x[i]+1),b.push_back(avg);
					se.insert({a.back(),b.back()});
				}
			}
			else
			{
				int avg=(x[i]+x[j])/2;
				if (se.find({avg,y[i]-1})==se.end())
				{
					u.push_back(i),v.push_back(j);
					a.push_back(avg),b.push_back(y[i]-1);
					se.insert({a.back(),b.back()});
				}
				else
				{
					u.push_back(i),v.push_back(j);
					a.push_back(avg),b.push_back(y[i]+1);
					se.insert({a.back(),b.back()});
				}
			}
			nei[j].erase(i);
		}
	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