Submission #1111694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111694		siewjh	Fountain Parks (IOI21_parks)	C++17	100 / 100	448 ms	48188 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
map<pair<int, int>, int> ctid;
set<pair<int, int>> bs;
vector<int> re1, re2, rbx, rby;
int par[MAXN], rnk[MAXN];
int root(int x){
	if (par[x] == -1) return x;
	else return par[x] = root(par[x]);
}
void join(int ra, int rb){
	if (rnk[ra] > rnk[rb]) swap(ra, rb);
	par[ra] = rb;
	if (rnk[ra] == rnk[rb]) rnk[rb]++;
}
bool check(int bx, int by, int n0x, int n0y, int n1x, int n1y){
	if (!ctid.count({n0x, n0y}) || !ctid.count({n1x, n1y})) return 0;
	int n0id = ctid[{n0x, n0y}], n1id = ctid[{n1x, n1y}];
	int r0 = root(n0id), r1 = root(n1id);
	if (r0 == r1) return 0;
	join(r0, r1);
	re1.push_back(n0id); re2.push_back(n1id); rbx.push_back(bx); rby.push_back(by);
	return 1;
}
int construct_roads(vector<int> xv, vector<int> yv) {
	memset(par, -1, sizeof(par));
	int nodes = xv.size();
	for (int i = 0; i < nodes; i++) ctid[{xv[i], yv[i]}] = i;
	for (auto &[loc, id] : ctid){
		auto &[x, y] = loc;
		if (ctid.count({x, y + 2})){
			bs.insert({x - 1, y + 1}); bs.insert({x + 1, y + 1});
		}
		if (ctid.count({x + 2, y})){
			bs.insert({x + 1, y - 1}); bs.insert({x + 1, y + 1});
		}
	}
	for (auto &[bx, by] : bs){
		int n0x, n0y, n1x, n1y;
		if ((bx + by) % 4 == 0){
			n0x = bx - 1; n1x = bx + 1; n0y = n1y = by - 1;
			if (check(bx, by, n0x, n0y, n1x, n1y)) continue;
			n0y = n1y = by + 1;
			check(bx, by, n0x, n0y, n1x, n1y);
		}
		else{
			n0x = n1x = bx - 1; n0y = by - 1; n1y = by + 1;
			if (check(bx, by, n0x, n0y, n1x, n1y)) continue;
			n0x = n1x = bx + 1;
			check(bx, by, n0x, n0y, n1x, n1y);
		}
	}
	if (re1.size() != nodes - 1) return 0;
	build(re1, re2, rbx, rby);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:55:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |  if (re1.size() != nodes - 1) return 0;
      |      ~~~~~~~~~~~^~~~~~~~~~~~

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