제출 #1251627

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251627		Zicrus	Obstacles for a Llama (IOI25_obstacles)	C++20	23 / 100	66 ms	14512 KiB

obstacles

#include <bits/stdc++.h>
#include "obstacles.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(34056237);
ll _ = 0;

struct union_find {
	vector<ll> lnk, sz;

	union_find() { }
	union_find(ll n) : lnk(n), sz(n, 1) {
		iota(all(lnk), 0);
	}

	ll find (ll a) {
		if (lnk[a] != a) lnk[a] = find(lnk[a]);
		return lnk[a];
	}

	bool merge(ll a, ll b) {
		a = find(a); b = find(b);
		if (a == b) return false;
		if (sz[a] < sz[b]) swap(a, b);
		lnk[b] = a;
		sz[a] += sz[b];
		return true;
	}
};

union_find dsu;

void initialize(vector<int> T, vector<int> H) {
	ll n = T.size(), m = H.size();
	dsu = union_find(n * m);
	auto safe = [&](ll i, ll j) -> bool {
		return T[i] > H[j];
	};
	auto get_id = [&](ll i, ll j) -> ll {
		return i * m + j;
	};
	for (ll i = 1; i < n; i++) {
		for (ll j = 0; j < m; j++) {
			if (safe(i, j) && safe(i-1, j)) dsu.merge(get_id(i, j), get_id(i-1, j));
		}
	}
	for (ll i = 0; i < n; i++) {
		for (ll j = 1; j < m; j++) {
			if (safe(i, j) && safe(i, j-1)) dsu.merge(get_id(i, j), get_id(i, j-1));
		}
	}
}

bool can_reach(int L, int R, int S, int D) {
	ll m = R + 1;
	return dsu.find(S) == dsu.find(D);
}

#ifdef TEST
#include "grader.cpp"
#endif

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17