제출 #1300050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300050		nikakh	장애물 (IOI25_obstacles)	C++17	23 / 100	80 ms	10824 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 ub = upper_bound(v.begin(), v.end(), S);
	return ub == v.end() || *ub > 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