10330 | 2024. 03. 31 10:41:18 | szil | Hegyi levegő | cpp17 | Elfogadva 100/100 | 916ms | 122424 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}, {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 | 16180 KiB | ||||
2 | Elfogadva | 8ms | 16420 KiB | ||||
subtask2 | 19/19 | ||||||
3 | Elfogadva | 13ms | 17244 KiB | ||||
4 | Elfogadva | 14ms | 17696 KiB | ||||
5 | Elfogadva | 14ms | 17852 KiB | ||||
6 | Elfogadva | 14ms | 17900 KiB | ||||
7 | Elfogadva | 13ms | 18096 KiB | ||||
8 | Elfogadva | 13ms | 18188 KiB | ||||
9 | Elfogadva | 13ms | 18392 KiB | ||||
10 | Elfogadva | 12ms | 18624 KiB | ||||
subtask3 | 20/20 | ||||||
11 | Elfogadva | 7ms | 17472 KiB | ||||
12 | Elfogadva | 8ms | 18056 KiB | ||||
13 | Elfogadva | 18ms | 18960 KiB | ||||
14 | Elfogadva | 145ms | 31780 KiB | ||||
15 | Elfogadva | 572ms | 80660 KiB | ||||
subtask4 | 20/20 | ||||||
16 | Elfogadva | 570ms | 80624 KiB | ||||
17 | Elfogadva | 605ms | 122016 KiB | ||||
18 | Elfogadva | 711ms | 72164 KiB | ||||
19 | Elfogadva | 722ms | 72856 KiB | ||||
20 | Elfogadva | 720ms | 72916 KiB | ||||
subtask5 | 31/31 | ||||||
21 | Elfogadva | 210ms | 41376 KiB | ||||
22 | Elfogadva | 228ms | 31588 KiB | ||||
23 | Elfogadva | 222ms | 31508 KiB | ||||
24 | Elfogadva | 226ms | 31404 KiB | ||||
25 | Elfogadva | 202ms | 32176 KiB | ||||
26 | Elfogadva | 215ms | 31424 KiB | ||||
27 | Elfogadva | 229ms | 31424 KiB | ||||
28 | Elfogadva | 207ms | 32188 KiB | ||||
29 | Elfogadva | 194ms | 32012 KiB | ||||
subtask6 | 10/10 | ||||||
30 | Elfogadva | 804ms | 122424 KiB | ||||
31 | Elfogadva | 913ms | 72916 KiB | ||||
32 | Elfogadva | 916ms | 73628 KiB | ||||
33 | Elfogadva | 893ms | 73596 KiB | ||||
34 | Elfogadva | 762ms | 81692 KiB | ||||
35 | Elfogadva | 836ms | 76524 KiB | ||||
36 | Elfogadva | 827ms | 72536 KiB | ||||
37 | Elfogadva | 879ms | 72512 KiB | ||||
38 | Elfogadva | 765ms | 81748 KiB | ||||
39 | Elfogadva | 694ms | 76732 KiB |