| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1299773 | theiulius | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include "obstacles.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
int n = 0, m = 0;
const int N = 2005;
pair<int, int> parent[4][N];
int sz[4][N];
int xs[4] = {1, 1, -1, -1}, ys[4] = {1, -1, 1, -1};
pair<int, int> find_set(pair<int, int> v) {
if (v == parent[v.ff][v.ss])
return v;
return parent[v.ff][v.ss] = find_set(parent[v.ff][v.ss]);
}
void make_set(pair<int, int> v) {
parent[v.ff][v.ss] = v;
sz[v.ff][v.ss] = 1;
}
void union_sets(pair<int, int> a, pair<int, int> b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (sz[a.ff][a.ss] < sz[b.ff][b.ss])
swap(a, b);
parent[b.ff][b.ss] = a;
sz[a.ff][a.ss] += sz[b.ff][b.ss];
}
}
void initialize(std::vector<int> t, std::vector<int> h){
n = t.size(); m = h.size();
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
make_set({i, j});
}
}
// t = 2, 1, 3
int j = 0, b = 1, last_i = -1, last_j = -1;
for (int i = 0; i < n; i++){
while (j < m && j >= 0){
if (t[i] > h[j]){
for (int k = 0; k < 4; k++){
int i1 = i + xs[k], j1 = j + ys[k];
if (i1 < 0 || i1 > n || j1 < 0 || j1 > m || t[i1] > h[j1]){
continue;
}
union_sets({i1, j1}, {i, j});
}
}
j += b;
}
j -= b;
b = -b;
}
}
bool can_reach(int l, int r, int s, int d){
if (find_set({0, s}) == find_set({0, d})){
return 1;
}
return 0;
}
int main() {
int N, M;
assert(2 == scanf("%d %d", &N, &M));
std::vector<int> T(N), H(M);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &T[i]));
for (int i = 0; i < M; i++)
assert(1 == scanf("%d", &H[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> L(Q), R(Q), S(Q), D(Q);
for (int i = 0; i < Q; i++)
assert(4 == scanf("%d %d %d %d", &L[i], &R[i], &S[i], &D[i]));
fclose(stdin);
std::vector<bool> A(Q);
initialize(T, H);
for (int i = 0; i < Q; i++)
A[i] = can_reach(L[i], R[i], S[i], D[i]);
for (int i = 0; i < Q; i++)
if (A[i])
printf("1\n");
else
printf("0\n");
fclose(stdout);
return 0;
}