10329 | 2024. 03. 31 10:39:49 | szil | Hegyi levegő | cpp17 | Elfogadva 100/100 | 958ms | 265992 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 600'000;
const pair<int, int> DIR[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<vector<int>> a;
int p[MAXN], s[MAXN], t[MAXN], d[MAXN];
int n, m, q;
int to_index(int i, int j) {
return (i-1)*m+j;
}
int holvan(int u) {
return p[u] == u ? u : holvan(p[u]);
}
void unio(int u, int v, int w) {
u = holvan(u); v = holvan(v);
if (u == v) return;
if (s[u] < s[v]) swap(u, v);
s[u] += s[v];
t[v] = w;
p[v] = u;
}
int calc_depth(int u) {
if (d[u] == -1) {
if (p[u] == u) d[u] = 0;
d[u] = 1 + calc_depth(p[u]);
}
return d[u];
}
int query(int u, int v) {
int ans = 0;
while (u != v) {
if (d[u] > d[v]) swap(u, v);
ans = max(ans, t[v]);
v = p[v];
}
return ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> q;
iota(p, p+MAXN, 0);
fill(s, s+MAXN, 1);
fill(d, d+MAXN, -1);
a.resize(n+1, vector<int>(m+1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
vector<array<int, 3>> edges;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (auto [dx, dy] : DIR) {
int nx = i+dx, ny = j+dy;
if (1 <= nx && nx <= n && 1 <= ny && ny <= m) {
int w = max(a[i][j], a[nx][ny]);
int p = to_index(i, j), q = to_index(nx, ny);
edges.push_back({w, p, q});
}
}
}
}
sort(edges.begin(), edges.end());
for (auto [w, u, v] : edges) {
unio(u, v, w);
}
for (int i = 1; i <= n*m; i++) {
calc_depth(i);
}
while (q--) {
int a, b, c, d; cin >> a >> b >> c >> d;
int p = to_index(a, b), q = to_index(c, d);
cout << query(p, q) << "\n";
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 8ms | 15908 KiB | ||||
2 | Elfogadva | 8ms | 16252 KiB | ||||
subtask2 | 19/19 | ||||||
3 | Elfogadva | 10ms | 17096 KiB | ||||
4 | Elfogadva | 13ms | 17544 KiB | ||||
5 | Elfogadva | 13ms | 17872 KiB | ||||
6 | Elfogadva | 13ms | 18156 KiB | ||||
7 | Elfogadva | 13ms | 18176 KiB | ||||
8 | Elfogadva | 13ms | 18508 KiB | ||||
9 | Elfogadva | 13ms | 18576 KiB | ||||
10 | Elfogadva | 10ms | 18912 KiB | ||||
subtask3 | 20/20 | ||||||
11 | Elfogadva | 7ms | 17832 KiB | ||||
12 | Elfogadva | 8ms | 18032 KiB | ||||
13 | Elfogadva | 17ms | 19548 KiB | ||||
14 | Elfogadva | 123ms | 28304 KiB | ||||
15 | Elfogadva | 455ms | 70408 KiB | ||||
subtask4 | 20/20 | ||||||
16 | Elfogadva | 439ms | 75448 KiB | ||||
17 | Elfogadva | 467ms | 121472 KiB | ||||
18 | Elfogadva | 717ms | 96972 KiB | ||||
19 | Elfogadva | 797ms | 103320 KiB | ||||
20 | Elfogadva | 755ms | 107952 KiB | ||||
subtask5 | 31/31 | ||||||
21 | Elfogadva | 190ms | 74028 KiB | ||||
22 | Elfogadva | 230ms | 72988 KiB | ||||
23 | Elfogadva | 231ms | 76668 KiB | ||||
24 | Elfogadva | 236ms | 80624 KiB | ||||
25 | Elfogadva | 181ms | 80008 KiB | ||||
26 | Elfogadva | 215ms | 87752 KiB | ||||
27 | Elfogadva | 231ms | 91504 KiB | ||||
28 | Elfogadva | 181ms | 90912 KiB | ||||
29 | Elfogadva | 194ms | 98864 KiB | ||||
subtask6 | 10/10 | ||||||
30 | Elfogadva | 691ms | 183208 KiB | ||||
31 | Elfogadva | 938ms | 166752 KiB | ||||
32 | Elfogadva | 958ms | 181052 KiB | ||||
33 | Elfogadva | 936ms | 193368 KiB | ||||
34 | Elfogadva | 663ms | 193280 KiB | ||||
35 | Elfogadva | 822ms | 218156 KiB | ||||
36 | Elfogadva | 820ms | 227740 KiB | ||||
37 | Elfogadva | 897ms | 240084 KiB | ||||
38 | Elfogadva | 642ms | 240972 KiB | ||||
39 | Elfogadva | 703ms | 265992 KiB |