# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1253107 | kkzyr | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
int parent[1000000];
int find(int x){
if (parent[x] == -1){
return x;
}
int ans = find(parent[x]);
parent[x] = ans;
return ans;
}
void merge(int x, int y){
int component1 = find(x), component2 = find(y);
if (component1 != component2){
parent[component1] = component2;
}
}
void initialize(std::vector<int> T, std::vector<int> H){
for (int i = 0;i < H.size();i++){
parent[i] = -1;
}
for (int i = 0;i < H.size();i++){
if (T[T.size() - 1] > H[i]){
if (i >= 1 and T[T.size() - 1] > H[i - 1]){
merge(i, i - 1);
}
if (i < (H.size() - 1) and T[T.size() - 1] > H[i + 1]){
merge(i, i + 1);
}
}
}
}