Submission #1047796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047796		vjudge1	Fountain Parks (IOI21_parks)	C++17	45 / 100	275 ms	49996 KiB

parks

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

#define ar array

const int dir[4][2] = {{2, 0}, {-2, 0}, {0, 2}, {0, -2}};

const int N = 3e5 + 20;

int X[N], Y[N];
map<ar<int, 2>, int > mp;

vector<int> U, V, A, B;
bool vis[N];

void dfs(int x){
	vis[x] = 1;
	for(int i = 0;i < 4;i++){
		if(mp.count(ar<int, 2>{X[x] + dir[i][0], Y[x] + dir[i][1]})){
			int u = mp[ar<int, 2>{X[x] + dir[i][0], Y[x] + dir[i][1]}];
			if(vis[u])continue;
			U.push_back(x);
			V.push_back(u);
			if(X[x] == X[u]){
				B.push_back({Y[x] + (Y[x] < Y[u] ? 1 : -1)});
				if((X[u] + Y[u]) & 2)A.push_back({X[x] + (Y[x] > Y[u] ? 1 : -1)});
				else A.push_back({X[x] + (Y[x] < Y[u] ? 1 : -1)});
			}else{
				A.push_back({X[x] + (X[x] < X[u] ? 1 : -1)});
				if((X[u] + Y[u]) & 2)B.push_back({Y[x] + (X[x] < X[u] ? 1 : -1)});
				else B.push_back({Y[x] + (X[x] > X[u] ? 1 : -1)});
			}
			dfs(u);
		}
	}
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = x.size();
	for(int i = 0;i < n;i++)X[i] = x[i], Y[i] = y[i];
    for(int i = 0;i < n;i++)mp[{x[i], y[i]}] = i;
	dfs(0);
	for(int i = 0;i < n;i++){
		if(!vis[i]){
			return 0;
		}
	}
	

	build(U, V, A, B);
	return 1;
	
}

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