Submission #1263652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263652		am_aadvik	Obstacles for a Llama (IOI25_obstacles)	C++20	37 / 100	74 ms	12332 KiB

obstacles

#include <iostream>
#include <vector>
using namespace std;

class DSU {
public:
	vector<int> p, rank;
	void init(int n) {
		p.clear();
		for (int i = 0; i <= n; ++i)
			p.push_back(i);
		rank.assign(n + 1, 1);
	}
	int fset(int x) { return (p[x] == x) ? x : p[x] = fset(p[x]); }
	bool iset(int x, int y) { return fset(x) == fset(y); }
	void uset(int x, int y) {
		x = fset(x), y = fset(y);
		if (x != y) {
			if (rank[x] > rank[y])
				swap(x, y);
			p[x] = y, rank[y] += rank[x];
		}
	}
};
DSU u;
vector<int> h, t;
int n, m;
int comp(int i, int j) { return (n <= 3? i * m + j: j); }
void initialize(vector<int> a, vector<int> b) {
	t = a, h = b, n = t.size(), m = h.size();
	u.init(((n <= 3)? n * m + n + m: m + 1));
	for(int i = ((n <= 3)? 0: n - 1); i < n; ++i)
		for (int j = 0; j < m; ++j) 
			if (t[i] > h[j]) {
				int di[] = { 0, 0, 1, -1 };
				int dj[] = { 1, -1, 0, 0 };
				for (int x = 0; x < 4; ++x) {
					int ni = i + di[x], nj = j + dj[x];
					if ((ni >= 0) && (nj >= 0) && (nj < m) && (ni < n))
						if (t[ni] > h[nj])
							u.uset(comp(i, j), comp(ni, nj));
				}
			}
}
bool can_reach(int l, int r, int s, int d) {
	return u.iset((0, s), comp(0, d));
}
/*int main() {
	initialize({ 2, 1, 3 }, { 0, 1, 2, 0 });
	cout << can_reach(0, 3, 1, 3) << endl;
	cout << can_reach(1, 3, 1, 3) << endl;
}*/

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