Mùa lũ (Đề tự luyện HSG Tin 12 – Bài 4)
Đề bài
Mùa lũ. Có $N$ xóm, nền xóm $i$ cao $h_i$; $M$ con đường hai chiều, đường $j$ nối $u_j, v_j$ và mất $c_j$ phút. Một hành trình đi qua các xóm $x_1, x_2, \dots, x_k$ có độ an toàn bằng $\min(h_{x_1}, \dots, h_{x_k})$ (tính cả xóm đầu và xóm cuối) và thời gian bằng tổng thời gian các con đường. Với mỗi câu hỏi $(s, t, T)$: trong các hành trình từ $s$ tới $t$ mất không quá $T$ phút, độ an toàn lớn nhất là bao nhiêu? Không có hành trình nào thì in $-1$ (nếu $s = t$, hành trình chỉ gồm xóm $s$, mất $0$ phút).
Dữ liệu vào: dòng đầu $N, M, Q$ ($1 \le N \le 300$, $0 \le M \le 50\,000$, $1 \le Q \le 10^5$); dòng hai $h_1, \dots, h_N$ ($1 \le h_i \le 10^9$); $M$ dòng $u_j, v_j, c_j$ ($u_j \ne v_j$, $1 \le c_j \le 10^9$); $Q$ dòng $s_i, t_i, T_i$ ($0 \le T_i \le 10^{12}$).
Kết quả: $Q$ dòng, mỗi dòng một đáp án.
- Subtask 1 (15%): $N \le 50$ và $Q \le 50$.
- Subtask 2 (25%): $Q \le 300$.
- Subtask 3 (25%): dãy $h$ có không quá $10$ giá trị khác nhau.
- Subtask 4 (35%): không có ràng buộc gì thêm.
7 8 4
8 9 4 7 7 5 3
4 7 9
4 6 3
3 5 8
1 6 9
2 3 4
5 7 2
1 3 3
3 4 8
4 1 14
5 4 11
1 5 20
1 4 115
3
4
4Câu 1: đi $4 \to 6 \to 1$ mất $12$ phút, nền các xóm $7, 5, 8$, an toàn $5$. Câu 2: $5 \to 7 \to 4$ mất $11$ phút, an toàn $3$ (đường $5 \to 3 \to 4$ an toàn $4$ nhưng mất $16$ phút). Câu 3: $1 \to 3 \to 5$ mất $11$ phút, an toàn $4$. Câu 4: $1 \to 3 \to 4$ mất đúng $11$ phút, an toàn $4$ (đường $1 \to 6 \to 4$ an toàn $5$ nhưng mất $12$ phút).
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Mùa lũLời mở đầu
Bài này có hai tiêu chí ngược nhau: muốn an toàn thì phải né các xóm nền thấp, mà né thì thường phải đi vòng, tốn thời gian. Câu 4 của ví dụ cho thấy rõ: đường $1 \to 6 \to 4$ an toàn $5$ nhưng mất $12$ phút, quá $T = 11$; đường nhanh $1 \to 3 \to 4$ chỉ an toàn $4$. Vì vậy không thể "tìm đường an toàn nhất" rồi "tìm đường nhanh nhất" riêng rẽ — phải gộp hai tiêu chí lại.
Nhận xét 1 – đổi câu hỏi thành câu hỏi "có/không". Cố định một ngưỡng $v$. Một hành trình có độ an toàn $\ge v$ khi và chỉ khi mọi xóm nó đi qua có $h \ge v$. Vậy: "có hành trình an toàn $\ge v$ mất không quá $T$ phút" $\iff$ trong đồ thị chỉ gồm các xóm có $h \ge v$, đường đi ngắn nhất từ $s$ tới $t$ (cả $s$, $t$ cũng phải có $h \ge v$) dài không quá $T$. Đáp án luôn là một trong các giá trị $h_i$ (độ an toàn là min của vài $h$), nên chỉ cần thử các ngưỡng $v \in \{h_1, \dots, h_N\}$.
Nhận xét 2 – tính đơn điệu. Hạ ngưỡng $v$ thì đồ thị chỉ được thêm xóm, đường ngắn nhất chỉ có thể ngắn đi. Nên nếu ngưỡng $v$ đạt thì mọi ngưỡng thấp hơn cũng đạt: đáp án là ngưỡng cao nhất còn đạt.
Nhận xét 3 – nút thắt của bài: vòng lặp $k$ của Floyd. Thuật toán Floyd–Warshall có một tính chất mà nhiều bạn học thuộc code nhưng ít để ý: sau khi vòng ngoài cùng đã chạy xong với $k = 0, 1, \dots, K$, giá trị $d[i][j]$ chính là đường ngắn nhất từ $i$ tới $j$ mà mọi xóm trung gian đều thuộc $\{0, 1, \dots, K\}$. Thứ tự các đỉnh trong vòng $k$ là do ta chọn! Nếu đánh số lại các xóm theo độ cao giảm dần (xóm cao nhất là số $0$), thì sau bước $K$ ta có đúng đường ngắn nhất "chỉ đi qua $K + 1$ xóm cao nhất" — tức là đồ thị ứng với ngưỡng $v = h$ của xóm thứ $K$. Chạy Floyd một lần, ta đi qua tất cả các ngưỡng từ cao xuống thấp!
Mỗi bước $k$ của Floyd "mở" thêm một xóm. Ngưỡng hiện tại chính là nền của xóm vừa mở; câu hỏi nào lần đầu thoả mãn ở bước nào thì đáp án là nền của xóm đó.
Nhận xét 4 – trả lời offline. Với câu hỏi $(s, t, T)$, đáp án là nền của xóm được mở ở bước đầu tiên mà cả $s$, $t$ đã được mở và $d[s][t] \le T$. Vì ta đọc hết câu hỏi trước rồi mới chạy Floyd (không cần trả lời ngay), mỗi bước $k$ chỉ việc kiểm tra các câu hỏi đang chờ. Câu nào đã có đáp án thì bỏ khỏi danh sách chờ.
Cách 1Thử mọi ngưỡng từ cao xuống thấp – O(Q · N · N²) · 15%
Theo nhận xét 1, với mỗi câu hỏi ta thử lần lượt các ngưỡng $v$ (các giá trị $h$ khác nhau) từ cao xuống thấp, bỏ qua các ngưỡng cao hơn $\min(h_s, h_t)$. Với mỗi ngưỡng, chạy Dijkstra trên các xóm có $h \ge v$; ngưỡng đầu tiên cho đường ngắn nhất $\le T$ chính là đáp án. Đồ thị có thể dày (tới $50\,000$ con đường giữa $300$ xóm) nên dùng Dijkstra $O(N^2)$ trên ma trận kề $w[u][v]$ (giữ con đường ngắn nhất nếu hai xóm có nhiều đường nối).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)1e18;
int n, m, q;
vector<ll> h;
vector<vector<ll>> w; // w[u][v]: thời gian con đường ngắn nhất nối thẳng u, v
// Dijkstra O(n^2), chỉ đi trên các xóm có h >= th
ll dijkstra(int s, int t, ll th) {
vector<ll> dist(n, INF);
vector<bool> done(n, false);
dist[s] = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int i = 0; i < n; i++)
if (!done[i] && h[i] >= th && (u == -1 || dist[i] < dist[u])) u = i;
if (u == -1 || dist[u] >= INF) break;
if (u == t) return dist[u];
done[u] = true;
for (int v = 0; v < n; v++)
if (h[v] >= th && w[u][v] < INF && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];
}
return dist[t];
}
int main() {
scanf("%d %d %d", &n, &m, &q);
h.resize(n);
for (auto &x : h) scanf("%lld", &x);
w.assign(n, vector<ll>(n, INF));
for (int e = 0; e < m; e++) {
int u, v; ll c;
scanf("%d %d %lld", &u, &v, &c);
u--; v--;
w[u][v] = w[v][u] = min(w[u][v], c);
}
vector<ll> vals = h;
sort(vals.rbegin(), vals.rend());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
while (q--) {
int u, v; ll T;
scanf("%d %d %lld", &u, &v, &T);
u--; v--;
ll ans = -1;
for (ll th : vals) { // thử ngưỡng từ cao xuống thấp
if (th > min(h[u], h[v])) continue;
if (dijkstra(u, v, th) <= T) { ans = th; break; }
}
printf("%lld\n", ans);
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
h = [int(x) for x in data[3:3 + n]]
p = 3 + n
INF = 10 ** 18
w = [[INF] * n for _ in range(n)]
for e in range(m):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; c = int(data[p + 2])
p += 3
if c < w[u][v]:
w[u][v] = c; w[v][u] = c
vals = sorted(set(h), reverse=True)
def dijkstra(s, t, th):
# Dijkstra O(n^2), chỉ đi trên các xóm có h >= th
dist = [INF] * n
done = [False] * n
dist[s] = 0
for _ in range(n):
u = -1
for i in range(n):
if not done[i] and h[i] >= th and (u == -1 or dist[i] < dist[u]):
u = i
if u == -1 or dist[u] >= INF:
break
if u == t:
return dist[u]
done[u] = True
wu = w[u]
for v in range(n):
if h[v] >= th and wu[v] < INF and dist[u] + wu[v] < dist[v]:
dist[v] = dist[u] + wu[v]
return dist[t]
out = []
for _ in range(q):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; T = int(data[p + 2])
p += 3
ans = -1
for th in vals: # thử ngưỡng từ cao xuống thấp
if th > min(h[u], h[v]):
continue
if dijkstra(u, v, th) <= T:
ans = th
break
out.append(ans)
print("\n".join(map(str, out)))
main()Với $N = Q = 50$ chỉ khoảng $6 \cdot 10^6$ phép tính. Nhưng ở subtask 2 ($N = Q = 300$) có thể phải thử gần $300$ ngưỡng cho mỗi câu hỏi — cỡ $8 \cdot 10^9$ phép tính, quá giờ.
Cách 2Chặt nhị phân trên ngưỡng – O(Q · log N · N²) · 40%
Nhận xét 2 nói rằng "ngưỡng $v$ đạt" là tính chất đơn điệu: đạt ở $v$ thì đạt ở mọi ngưỡng thấp hơn. Vậy thay vì thử lần lượt, ta chặt nhị phân trên mảng các giá trị $h$ đã sắp xếp tăng dần, tìm vị trí cuối cùng còn đạt. Mỗi câu hỏi chỉ cần khoảng $\log_2 300 \approx 9$ lần Dijkstra.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)1e18;
int n, m, q;
vector<ll> h;
vector<vector<ll>> w;
// Dijkstra O(n^2), chỉ đi trên các xóm có h >= th
ll dijkstra(int s, int t, ll th) {
vector<ll> dist(n, INF);
vector<bool> done(n, false);
dist[s] = 0;
for (int it = 0; it < n; it++) {
int u = -1;
for (int i = 0; i < n; i++)
if (!done[i] && h[i] >= th && (u == -1 || dist[i] < dist[u])) u = i;
if (u == -1 || dist[u] >= INF) break;
if (u == t) return dist[u];
done[u] = true;
for (int v = 0; v < n; v++)
if (h[v] >= th && w[u][v] < INF && dist[u] + w[u][v] < dist[v]) dist[v] = dist[u] + w[u][v];
}
return dist[t];
}
int main() {
scanf("%d %d %d", &n, &m, &q);
h.resize(n);
for (auto &x : h) scanf("%lld", &x);
w.assign(n, vector<ll>(n, INF));
for (int e = 0; e < m; e++) {
int u, v; ll c;
scanf("%d %d %lld", &u, &v, &c);
u--; v--;
w[u][v] = w[v][u] = min(w[u][v], c);
}
vector<ll> vals = h;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
while (q--) {
int u, v; ll T;
scanf("%d %d %lld", &u, &v, &T);
u--; v--;
// ngưỡng càng thấp càng dễ đạt -> chặt nhị phân trên các ngưỡng <= min(h[u], h[v])
int lo = 0, hi = upper_bound(vals.begin(), vals.end(), min(h[u], h[v])) - vals.begin() - 1;
ll ans = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (dijkstra(u, v, vals[mid]) <= T) { ans = vals[mid]; lo = mid + 1; }
else hi = mid - 1;
}
printf("%lld\n", ans);
}
}import sys
from bisect import bisect_right
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
h = [int(x) for x in data[3:3 + n]]
p = 3 + n
INF = 10 ** 18
w = [[INF] * n for _ in range(n)]
for e in range(m):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; c = int(data[p + 2])
p += 3
if c < w[u][v]:
w[u][v] = c; w[v][u] = c
vals = sorted(set(h))
def dijkstra(s, t, th):
# Dijkstra O(n^2), chỉ đi trên các xóm có h >= th
dist = [INF] * n
done = [False] * n
dist[s] = 0
for _ in range(n):
u = -1
for i in range(n):
if not done[i] and h[i] >= th and (u == -1 or dist[i] < dist[u]):
u = i
if u == -1 or dist[u] >= INF:
break
if u == t:
return dist[u]
done[u] = True
wu = w[u]
for v in range(n):
if h[v] >= th and wu[v] < INF and dist[u] + wu[v] < dist[v]:
dist[v] = dist[u] + wu[v]
return dist[t]
out = []
for _ in range(q):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; T = int(data[p + 2])
p += 3
# ngưỡng càng thấp càng dễ đạt -> chặt nhị phân
lo, hi = 0, bisect_right(vals, min(h[u], h[v])) - 1
ans = -1
while lo <= hi:
mid = (lo + hi) // 2
if dijkstra(u, v, vals[mid]) <= T:
ans = vals[mid]; lo = mid + 1
else:
hi = mid - 1
out.append(ans)
print("\n".join(map(str, out)))
main()Subtask 2 chỉ còn khoảng $300 \cdot 9 \cdot 9 \cdot 10^4 \approx 2{,}4 \cdot 10^8$ phép tính đơn giản. Nhưng khi $Q = 10^5$, con số này lên tới $8 \cdot 10^{10}$: mỗi câu hỏi vẫn phải tự chạy Dijkstra của riêng nó, mà các câu hỏi thì quá nhiều.
Cách 3Ít mức nền: Floyd cho từng mức – O(L · N³ + Q · L) · 40%
Ở subtask 3 chỉ có $L \le 10$ mức nền khác nhau. Các câu hỏi rất nhiều nhưng các đồ thị cần xét thì ít: chỉ có $L$ đồ thị (mỗi mức một đồ thị). Vậy với mỗi mức $v$, ta chạy Floyd một lần trên các xóm có $h \ge v$ để có khoảng cách giữa mọi cặp xóm, lưu lại thành bảng $D_v$. Sau đó mỗi câu hỏi chỉ cần duyệt $L$ mức từ cao xuống thấp và tra bảng $O(1)$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)1e18;
int main() {
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
vector<ll> h(n);
for (auto &x : h) scanf("%lld", &x);
vector<vector<ll>> w(n, vector<ll>(n, INF));
for (int i = 0; i < n; i++) w[i][i] = 0;
for (int e = 0; e < m; e++) {
int u, v; ll c;
scanf("%d %d %lld", &u, &v, &c);
u--; v--;
w[u][v] = w[v][u] = min(w[u][v], c);
}
vector<ll> vals = h;
sort(vals.rbegin(), vals.rend());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int L = vals.size();
// D[t]: Floyd trên các xóm có h >= vals[t]
vector<vector<vector<ll>>> D(L);
for (int t = 0; t < L; t++) {
auto d = w;
for (int k = 0; k < n; k++) {
if (h[k] < vals[t]) continue;
for (int i = 0; i < n; i++) {
if (h[i] < vals[t] || d[i][k] >= INF) continue;
for (int j = 0; j < n; j++)
if (h[j] >= vals[t] && d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
}
}
D[t] = d;
}
while (q--) {
int u, v; ll T;
scanf("%d %d %lld", &u, &v, &T);
u--; v--;
ll ans = -1;
for (int t = 0; t < L; t++)
if (vals[t] <= min(h[u], h[v]) && D[t][u][v] <= T) { ans = vals[t]; break; }
printf("%lld\n", ans);
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
h = [int(x) for x in data[3:3 + n]]
p = 3 + n
INF = 10 ** 18
w = [[INF] * n for _ in range(n)]
for i in range(n):
w[i][i] = 0
for e in range(m):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; c = int(data[p + 2])
p += 3
if c < w[u][v]:
w[u][v] = c; w[v][u] = c
vals = sorted(set(h), reverse=True)
D = []
for th in vals:
# Floyd trên các xóm có h >= th (xóm thấp hơn thì coi như không tồn tại)
ok = [x >= th for x in h]
d = [[w[i][j] if ok[i] and ok[j] else INF for j in range(n)] for i in range(n)]
for k in range(n):
if not ok[k]:
continue
dk = d[k]
for i in range(n):
di = d[i]
dik = di[k]
if dik >= INF:
continue
for j in range(n):
if dik + dk[j] < di[j]:
di[j] = dik + dk[j]
D.append(d)
out = []
for _ in range(q):
u = int(data[p]) - 1; v = int(data[p + 1]) - 1; T = int(data[p + 2])
p += 3
ans = -1
for t in range(len(vals)):
if vals[t] <= min(h[u], h[v]) and D[t][u][v] <= T:
ans = vals[t]
break
out.append(ans)
print("\n".join(map(str, out)))
main()Khi các $h_i$ khác nhau hết thì $L = N = 300$: chạy $300$ lần Floyd là cỡ $300 \cdot 2{,}7 \cdot 10^7 \approx 8 \cdot 10^9$ phép tính. Bộ test của subtask 2 và 4 đều có $h$ gần như khác nhau hết nên Cách 3 quá giờ ở đó. Nhưng hãy để ý: Floyd cho mức thấp hơn lại làm lại từ đầu những việc mà Floyd cho mức cao hơn đã làm rồi. Đó là gợi ý cho Cách 4.
Cách 4Một lần Floyd theo nền giảm dần, trả lời offline – O(N³ + M + Q) · 100%
Ghép nhận xét 3 và 4:
- Sắp xếp các xóm theo nền giảm dần, đánh số lại:
id[x]là thứ hạng của xóm $x$ (xóm cao nhất cóid = 0). Mọi chỉ số trong ma trận $d$ đều dùng số mới. - Đọc các câu hỏi. Câu hỏi $(s, t)$ đổi thành cặp $a = \min(\text{id}[s], \text{id}[t])$, $b = \max(\ldots)$. Hai xóm $s, t$ cùng được mở kể từ bước $k = b$, nên ta cất câu hỏi vào
at[b]. - Chạy Floyd với $k = 0, 1, \dots, N - 1$. Sau khi cập nhật ma trận ở bước $k$, đưa các câu hỏi trong
at[k]vào danh sách chờact, rồi duyệt danh sách chờ: câu nào có $d[a][b] \le T$ thì đáp án là $h$ của xóm vừa mở (h[ord[k]]) và bỏ khỏi danh sách; câu nào chưa đạt thì giữ lại. - Câu hỏi nào tới cuối vẫn còn trong danh sách chờ thì đáp án là $-1$.
Vì sao đúng? Ở bước $k$, ma trận $d$ đúng bằng đường ngắn nhất qua các xóm $0..k$ (nhận xét 3). Cả hai đầu $a, b \le k$ cũng đã mở. Các xóm $0..k$ chính là mọi xóm có nền $\ge h[\text{ord}[k]]$ — trừ khi có nhiều xóm cùng nền: khi đó vài xóm cùng nền có thể chưa mở. Nhưng điều này không làm sai đáp án: nếu câu hỏi đạt ở bước nào đó trong nhóm cùng nền thì đáp án đều bằng giá trị nền chung đó; nếu chưa đạt thì tới bước cuối của nhóm (đã mở đủ cả nhóm) sẽ được kiểm tra lại. Và bước đầu tiên đạt cho ra ngưỡng cao nhất còn đạt (nhận xét 2).
Một hành trình có thể đi qua $299$ con đường, mỗi con dài tới $10^9$ phút: tổng lên tới khoảng $3 \cdot 10^{11}$, vượt int. Đặt $\text{INF} = 10^{18}$ và bỏ qua hàng $i$ khi $d[i][k] \ge \text{INF}$ thì phép cộng $d[i][k] + d[k][j] \le 2 \cdot 10^{18}$ vẫn nằm gọn trong long long.
Mô phỏng dưới đây chạy đúng các bước trên với ví dụ của đề (em có thể sửa dữ liệu): mỗi bước mở thêm một xóm, bảng bên dưới cho biết khoảng cách hiện tại của từng câu hỏi.
Code chuẩn (bản Python gom các câu hỏi cùng một cặp xóm lại, sắp theo $T$, để mỗi bước chỉ kiểm tra một lần cho mỗi cặp — cùng ý tưởng, chỉ nhanh hơn):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)1e18;
int main() {
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
vector<ll> h(n);
for (auto &x : h) scanf("%lld", &x);
// đánh số lại: xóm cao nhất là 0, thấp nhất là n-1
vector<int> ord(n), id(n);
iota(ord.begin(), ord.end(), 0);
stable_sort(ord.begin(), ord.end(), [&](int a, int b) { return h[a] > h[b]; });
for (int k = 0; k < n; k++) id[ord[k]] = k;
vector<vector<ll>> d(n, vector<ll>(n, INF));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (int e = 0; e < m; e++) {
int u, v; ll c;
scanf("%d %d %lld", &u, &v, &c);
u = id[u - 1]; v = id[v - 1];
if (c < d[u][v]) d[u][v] = d[v][u] = c;
}
vector<ll> T(q), ans(q, -1);
vector<int> pa(q), pb(q);
vector<vector<int>> at(n); // at[k]: các câu hỏi có max(a, b) = k
for (int i = 0; i < q; i++) {
int u, v;
scanf("%d %d %lld", &u, &v, &T[i]);
int a = id[u - 1], b = id[v - 1];
if (a > b) swap(a, b);
pa[i] = a; pb[i] = b;
at[b].push_back(i);
}
vector<int> act, nxt; // các câu hỏi chưa trả lời mà hai đầu đã "mở"
for (int k = 0; k < n; k++) {
// Floyd: cho phép đi qua xóm k
for (int i = 0; i < n; i++) {
ll dik = d[i][k];
if (dik >= INF) continue;
ll *ri = d[i].data(), *rk = d[k].data();
for (int j = 0; j < n; j++)
if (dik + rk[j] < ri[j]) ri[j] = dik + rk[j];
}
for (int i : at[k]) act.push_back(i);
nxt.clear();
for (int i : act) {
if (d[pa[i]][pb[i]] <= T[i]) ans[i] = h[ord[k]];
else nxt.push_back(i);
}
swap(act, nxt);
}
string out;
for (int i = 0; i < q; i++) out += to_string(ans[i]) + '\n';
fputs(out.c_str(), stdout);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m, q = int(data[0]), int(data[1]), int(data[2])
h = [int(x) for x in data[3:3 + n]]
p = 3 + n
# đánh số lại: xóm cao nhất là 0, thấp nhất là n-1
ord_ = sorted(range(n), key=lambda i: -h[i])
idx = [0] * n
for k in range(n):
idx[ord_[k]] = k
INF = 10 ** 18
d = [[INF] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for e in range(m):
u = idx[int(data[p]) - 1]; v = idx[int(data[p + 1]) - 1]; c = int(data[p + 2])
p += 3
if c < d[u][v]:
d[u][v] = c; d[v][u] = c
T = [0] * q
grp = {} # cặp (a, b), a <= b -> danh sách câu hỏi
for i in range(q):
a = idx[int(data[p]) - 1]; b = idx[int(data[p + 1]) - 1]; T[i] = int(data[p + 2])
p += 3
if a > b:
a, b = b, a
key = a * n + b
if key in grp:
grp[key].append(i)
else:
grp[key] = [i]
at = [[] for _ in range(n)] # at[k]: các cặp có b = max(a, b) = k
for key in grp:
grp[key].sort(key=T.__getitem__) # T tăng dần, lấy từ cuối
at[key % n].append(key)
ans = [-1] * q
act = [] # các cặp còn câu hỏi chưa trả lời, hai đầu đã "mở"
rng = range(n)
for k in rng:
# Floyd: cho phép đi qua xóm k
rk = d[k]
for i in rng:
ri = d[i]
dik = ri[k]
if dik >= INF:
continue
d[i] = [x if x <= y + dik else y + dik for x, y in zip(ri, rk)]
act.extend(at[k])
hk = h[ord_[k]]
nxt = []
for key in act:
dist = d[key // n][key % n]
lst = grp[key]
while lst and T[lst[-1]] >= dist:
ans[lst.pop()] = hk
if lst:
nxt.append(key)
act = nxt
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – thử mọi ngưỡng, mỗi ngưỡng một lần Dijkstra | Đúng | TLE | TLE | TLE | 15 |
| Cách 2 – chặt nhị phân ngưỡng + Dijkstra | Đúng | Đúng | TLE | TLE | 40 |
| Cách 3 – Floyd riêng cho từng mức nền | Đúng | TLE | Đúng | TLE | 40 |
| Cách 4 – một lần Floyd theo nền giảm dần, offline (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | 100 |
Sai: lưu khoảng cách bằng int | 3/7 | 3/7 | 3/7 | 1/9 | 31,75 |
| Sai: tham lam – lấy đường an toàn nhất, quá giờ thì lấy đường nhanh nhất | 3/7 | 0/7 | TLE | TLE | 6,43 |
| Sai: quên rằng xóm đầu/cuối cũng tính vào độ an toàn | 2/7 | 0/7 | 0/7 | 0/9 | 4,29 |
| Sai: khi mở xóm k chỉ cập nhật các cặp xóm đã mở | 2/7 | 0/7 | 0/7 | 0/9 | 4,29 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: 30 test (subtask 1: 7 test, subtask 2: 7 test, subtask 3: 7 test, subtask 4: 9 test), chấm kiểu "đúng test nào được điểm test đó". Mọi test từ subtask 2 trở đi có $N = 300$; subtask 2 có $Q = 300$ với hai đầu câu hỏi thường là xóm cao và $T$ rất sát (đáp án thấp hoặc $-1$) nên thử lần lượt từng ngưỡng chắc chắn quá giờ; subtask 3, 4 có $Q = 10^5$. Đồ thị có loại dày (gần $45\,000$ con đường, có cả đường trùng), loại thưa, có loại không liên thông; con đường càng qua xóm cao thì càng chậm để hai tiêu chí thật sự "giằng co" nhau; thời gian mỗi con đường tới $10^9$ nên khoảng cách vượt int. Lời giải chuẩn C++ chạy tối đa khoảng 0,4 giây. Bản Python nên nộp bằng PyPy 3 (giới hạn 5 giây).
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét