Submission #435013

#	Time	Username	Problem	Language	Result	Execution time	Memory
435013		frodakcin	Fountain Parks (IOI21_parks)	C++17	100 / 100	1294 ms	68040 KiB

parks

#include "parks.h"

#include <map>
#include <set>
#include <utility>

using pii = std::pair<int, int>;
#define ff first
#define ss second

const int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
const int MN = 2e5+10;

int ctr, N;
bool v[MN];
pii pt[MN];
std::map<pii, int> map;
std::set<pii> bloc;
void dfs(int n)
{
	if(v[n]) return;
	v[n]=1, ++ctr;
	pii x = pt[n];
	for(int i=0;i<4;++i)
	{
		pii o(x.ff+2*dx[i], x.ss+2*dy[i]);
		if(map.find(o) != map.end())
			dfs(map[o]);
	}
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	N = x.size();
	for(int i=0;i<N;++i)
	{
		pt[i]={x[i], y[i]};
		map[pt[i]]=i;
		bloc.insert({x[i]-1, y[i]-1});
		bloc.insert({x[i]+1, y[i]-1});
		bloc.insert({x[i]-1, y[i]+1});
		bloc.insert({x[i]+1, y[i]+1});
	}
	dfs(0);
	if(ctr < N) return 0;

	std::vector<int> u, v, a, b;
	for(auto x:bloc)
	{
		int d = x.ff+x.ss&3 ? 1 : -1;
		pii p1(x.ff+1, x.ss+d);
		pii p2(x.ff-d, x.ss+1);
		pii p3(x.ff-1, x.ss-d);
		pii p4(x.ff+d, x.ss-1);
		if(map.find(p1) != map.end() && map.find(p2) != map.end())
			u.push_back(map[p1]), v.push_back(map[p2]), a.push_back(x.ff), b.push_back(x.ss);
		else if(map.find(p3) != map.end() && map.find(p4) != map.end())
			u.push_back(map[p3]), v.push_back(map[p4]), a.push_back(x.ff), b.push_back(x.ss);
	}

	build(u, v, a, b);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:49:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   49 |   int d = x.ff+x.ss&3 ? 1 : -1;
      |               ^

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