Submission #1300046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300046		nikakh	Obstacles for a Llama (IOI25_obstacles)	C++17	23 / 100	112 ms	10844 KiB

obstacles

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

struct dsu{
	vector<int> parent, size;
	void init(int n){
		parent.resize(n);
		size.assign(n, 1);
		iota(parent.begin(), parent.end(), 0);
	}
	int find(int v){
		if(v == parent[v]) return v;
		return parent[v] = find(parent[v]);
	}
	void join(int a, int b){
		a = find(a);
		b = find(b);
		if(a == b) return;
		if(size[a] < size[b]) swap(a, b);
		parent[b] = a;
		size[a] += size[b];
	}
};

dsu D;
vector<int> T, v;
int n, m;

int id(int r, int c, int &M){
	return r * M + c;
}

void initialize(vector<int> T, vector<int> H) {
	n = (int)T.size(), m = (int)H.size();
	if(n <= 3){
		D.init(n * m);
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(T[i] > H[j]){
					if(i && T[i - 1] > H[j]) D.join(id(i, j, m), id(i - 1, j, m));
					if(j && T[i] > H[j - 1]) D.join(id(i, j, m), id(i, j - 1, m));
				}
			}
		}
	}
	::T = T;
	for(int i = 0; i < m; i++){
		if(H[i] >= T[n - 1]) v.push_back(i);
	}
}

bool can_reach(int L, int R, int S, int D) {
	if(D > S) swap(S, D);
	if(n == 1 || T == vector<int> {2, 1, 3}){
		return ::D.find(S) == ::D.find(D);
	}
	auto LB = lower_bound(v.begin(), v.end(), S);
	return LB == v.end() || *LB > D;
}

• 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