Tuyến đua ghe (Đề tự luyện HSG Tin quốc gia – Bài 2)
Đề bài
Tuyến đua ghe
Có $N$ bến ghe nối với nhau bởi $N - 1$ đoạn kênh tạo thành một cây, đoạn thứ $i$ nối $u_i, v_i$ và dài $w_i$. Một tuyến đua là đường đi duy nhất giữa hai bến khác nhau $u, v$ (không phân biệt chiều). Gọi $L$ là tổng chiều dài và $D$ là chiều dài đoạn dài nhất trên tuyến. Tuyến cân bằng nếu $2D < L$ (đoạn dài nhất ngắn hơn hẳn tổng các đoạn còn lại). Đếm số tuyến cân bằng.
Dữ liệu vào: dòng đầu $N$ $(1 \le N \le 2\cdot 10^5)$; $N - 1$ dòng sau mỗi dòng $u_i, v_i, w_i$ $(1 \le w_i \le 10^9)$.
Kết quả: số tuyến đua cân bằng.
- Subtask 1 (15%): $N \le 2000$.
- Subtask 2 (20%): mọi $w_i$ bằng nhau.
- Subtask 3 (25%): đoạn kênh thứ $i$ nối bến $i$ và $i+1$ (đường thẳng).
- Subtask 4 (40%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1,5 giây, Python/PyPy 5 giây.
6
1 2 3
2 3 4
3 4 2
2 5 5
5 6 13Ba tuyến cân bằng: $\{1,4\}$ (đoạn $3,4,2$), $\{4,5\}$ (đoạn $2,4,5$), $\{4,6\}$ (đoạn $2,4,5,1$). Tuyến $\{3,6\}$ có $2 \cdot 5 = 10 = L$ nên không cân bằng; $\{1,6\}$ có $10 > 9$; các tuyến $1$–$2$ đoạn không bao giờ cân bằng.
5
1 2 2
2 3 3
3 4 4
4 5 12Hai tuyến cân bằng là $\{1,4\}$ và $\{1,5\}$. Tuyến $\{2,5\}$ có các đoạn $3, 4, 1$, $2\cdot 4 = 8 = L$ nên không cân bằng.
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 Tuyến đua gheLời mở đầu
Điều kiện $2D < L$ chính là bất đẳng thức đa giác quen thuộc: các đoạn kênh trên tuyến ghép được thành một đa giác (không suy biến) khi và chỉ khi cạnh dài nhất nhỏ hơn tổng các cạnh còn lại. Vài nhận xét đầu tiên:
- Tuyến $1$ đoạn: $2D = 2L > L$. Tuyến $2$ đoạn $a \le b$: $2b \ge a + b$. Vậy tuyến cân bằng phải có ít nhất 3 đoạn.
- Có $\binom{N}{2}$ tuyến tất cả. Đếm phần bù – các tuyến xấu ($2D \ge L$) – sẽ tiện hơn, vì "xấu" nghĩa là có một đoạn "áp đảo", ta sẽ khai thác điều này.
- Dấu bằng là bẫy: tuyến $3, 4, 1$ có $2 \cdot 4 = 8 = L$ là xấu (đa giác bẹp). Nhầm thành $2D \le L$ là mất gần hết điểm.
Cây của ví dụ 1. Số trên cạnh là chiều dài đoạn kênh.
Lộ trình:
Cách 1Duyệt từ mọi bến – O(N²) · 15%
Từ mỗi bến $u$, duyệt cây (DFS/BFS bằng ngăn xếp) và mang theo hai đại lượng của đường $u \to x$: tổng $S[x]$ và đoạn dài nhất $M[x]$. Khi đi qua cạnh $x \to y$ dài $w$: $S[y] = S[x] + w$, $M[y] = \max(M[x], w)$. Mỗi cặp chỉ đếm một lần (khi $x > u$) nếu $2M[x] < S[x]$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
scanf("%d", &n);
vector<vector<pair<int, ll>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v; ll w;
scanf("%d %d %lld", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
ll ans = 0;
vector<ll> S(n + 1), M(n + 1);
vector<int> par(n + 1);
for (int u = 1; u <= n; u++) {
// duyet tu u: S = tong do dai, M = doan dai nhat tren duong u -> v
vector<int> st = {u};
par[u] = 0; S[u] = 0; M[u] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x > u && 2 * M[x] < S[x]) ans++; // moi cap {u, x} chi dem khi x > u
for (auto [y, w] : g[x]) {
if (y == par[x]) continue;
par[y] = x; S[y] = S[x] + w; M[y] = max(M[x], w);
st.push_back(y);
}
}
}
printf("%lld\n", ans);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
g = [[] for _ in range(n + 1)]
p = 1
for i in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
g[u].append((v, w))
g[v].append((u, w))
ans = 0
S = [0] * (n + 1); M = [0] * (n + 1); par = [0] * (n + 1)
for u in range(1, n + 1):
# duyet tu u: S = tong do dai, M = doan dai nhat tren duong u -> v
st = [u]
par[u] = 0; S[u] = 0; M[u] = 0
while st:
x = st.pop()
if x > u and 2 * M[x] < S[x]:
ans += 1
sx = S[x]; mx = M[x]; px = par[x]
for y, w in g[x]:
if y == px:
continue
par[y] = x; S[y] = sx + w; M[y] = mx if mx > w else w
st.append(y)
print(ans)
main()wrong_tranint.cpp để tổng ở kiểu int mất khoảng một nửa số test.Cách 2Khi mọi đoạn bằng nhau – O(N) · 35%
Nếu mọi $w_i = w$ thì tuyến $k$ đoạn có $L = kw$, $D = w$, cân bằng $\iff 2w < kw \iff k \ge 3$. Vậy chỉ cần trừ khỏi $\binom{N}{2}$ các cặp cách nhau $1$ đoạn ($N-1$ cặp) và $2$ đoạn. Cặp cách $2$ đoạn có đúng một "đỉnh giữa" $v$ và là hai hàng xóm bất kỳ của $v$, nên có $\sum_v \binom{\deg v}{2}$ cặp:
$$\text{Đáp án} = \binom{N}{2} - (N - 1) - \sum_{v} \binom{\deg v}{2}.$$
Code dưới đây ghép với Cách 1 (dữ liệu nào không có trọng số bằng nhau thì chạy Cách 1) nên ăn được subtask 1 + 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> eu, ev;
vector<ll> ew;
ll brute() { // Cach 1: duyet tu moi dinh, O(N^2)
vector<vector<pair<int, ll>>> g(n + 1);
for (int i = 0; i < n - 1; i++) { g[eu[i]].push_back({ev[i], ew[i]}); g[ev[i]].push_back({eu[i], ew[i]}); }
ll ans = 0;
vector<ll> S(n + 1), M(n + 1);
vector<int> par(n + 1);
for (int u = 1; u <= n; u++) {
vector<int> st = {u};
par[u] = 0; S[u] = 0; M[u] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x > u && 2 * M[x] < S[x]) ans++;
for (auto [y, w] : g[x]) {
if (y == par[x]) continue;
par[y] = x; S[y] = S[x] + w; M[y] = max(M[x], w);
st.push_back(y);
}
}
}
return ans;
}
ll equalWeights() { // Cach 2: moi doan bang nhau
vector<ll> deg(n + 1, 0);
for (int i = 0; i < n - 1; i++) { deg[eu[i]]++; deg[ev[i]]++; }
ll ans = (ll)n * (n - 1) / 2 - (n - 1); // bo cac cap ke nhau (1 doan)
for (int v = 1; v <= n; v++) ans -= deg[v] * (deg[v] - 1) / 2; // bo cac cap cach 2 doan
return ans;
}
int main() {
scanf("%d", &n);
eu.resize(n); ev.resize(n); ew.resize(n);
bool same = true;
for (int i = 0; i < n - 1; i++) {
scanf("%d %d %lld", &eu[i], &ev[i], &ew[i]);
if (ew[i] != ew[0]) same = false;
}
printf("%lld\n", same ? equalWeights() : brute());
return 0;
}import sys
def brute(n, edges):
# Cach 1: duyet tu moi dinh, O(N^2)
g = [[] for _ in range(n + 1)]
for u, v, w in edges:
g[u].append((v, w)); g[v].append((u, w))
ans = 0
S = [0] * (n + 1); M = [0] * (n + 1); par = [0] * (n + 1)
for u in range(1, n + 1):
st = [u]; par[u] = 0; S[u] = 0; M[u] = 0
while st:
x = st.pop()
if x > u and 2 * M[x] < S[x]:
ans += 1
sx = S[x]; mx = M[x]; px = par[x]
for y, w in g[x]:
if y == px:
continue
par[y] = x; S[y] = sx + w; M[y] = mx if mx > w else w
st.append(y)
return ans
def equal_weights(n, edges):
# Cach 2: moi doan bang nhau -> tuyen tot <=> co it nhat 3 doan
deg = [0] * (n + 1)
for u, v, w in edges:
deg[u] += 1; deg[v] += 1
ans = n * (n - 1) // 2 - (n - 1)
for d in deg:
ans -= d * (d - 1) // 2
return ans
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
edges = [(int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])) for i in range(n - 1)]
same = all(e[2] == edges[0][2] for e in edges)
print(equal_weights(n, edges) if same else brute(n, edges))
main()Cách 3Đường thẳng: chia để trị + "mẹo nửa đường" – O(N log² N) · 60%
Khi các bến nằm trên một đường thẳng, dãy đoạn kênh là mảng $w_1, w_2, \ldots, w_{N-1}$ và mỗi tuyến là một đoạn con liên tiếp. Ta đếm đoạn con xấu ($2\max \ge$ tổng) bằng chia để trị: chia mảng ở giữa $mid$, đếm đệ quy hai nửa, rồi đếm các đoạn con cắt qua điểm giữa. Mỗi đoạn con cắt qua gồm một hậu tố $x$ của nửa trái (kết thúc ở $mid$) và một tiền tố $y$ của nửa phải. Với mỗi "nửa đường" ta biết tổng $s$ và max $m$.
Đoạn ghép xấu $\iff 2\max(m_x, m_y) \ge s_x + s_y$. Có hai đại lượng max và tổng đan vào nhau – thoạt nhìn phải làm đếm 2 chiều (sắp theo max rồi dùng cây Fenwick theo tổng). Nhưng có một mẹo rất gọn. Đặt
$$t_x = 2m_x - s_x \quad (\text{"độ áp đảo" của nửa } x).$$
(1) Nếu $s_y \le t_x$ thì tự động $m_y \le m_x$, và đoạn ghép xấu. Thật vậy: $m_y \le s_y \le t_x = 2m_x - s_x \le m_x$ (vì $s_x \ge m_x$). Khi đó $\max = m_x$ và $2m_x \ge s_x + s_y$.
(2) Ngược lại, nếu đoạn ghép xấu và $m_x \ge m_y$ thì $2m_x \ge s_x + s_y$, tức là $s_y \le t_x$.
Vậy: đoạn ghép xấu $\iff s_y \le t_x$ hoặc $s_x \le t_y$. Không cần so sánh max nữa! Hai điều kiện cùng đúng chỉ khi $s_x = m_x = s_y = m_y$, tức là hai nửa đều là đúng một đoạn và hai đoạn này dài bằng nhau (tuyến 2 đoạn bằng nhau, bị đếm 2 lần).
Do đó số đoạn xấu cắt qua $mid$ $= \#\{(x, y): s_y \le t_x\} + \#\{(x, y): s_x \le t_y\} - [w_{mid} = w_{mid+1}]$. Mỗi số đếm "bao nhiêu $s$ không vượt quá mỗi $t$" làm bằng sắp xếp hai dãy rồi hai con trỏ. Mỗi tầng chia để trị tốn $O(N \log N)$, có $\log N$ tầng.
Mô phỏng một bước ghép (chỉ phần cắt qua điểm giữa, đối chiếu với cách đếm trực tiếp):
Code ghép cả Cách 1 và Cách 2 (dữ liệu không phải đường thẳng thì quay về hai cách trước):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> eu, ev;
vector<ll> ew, w; // w[1..n-1]: do dai cac doan kenh theo thu tu tren duong thang
ll bad = 0;
ll brute() { // Cach 1: duyet tu moi dinh, O(N^2)
vector<vector<pair<int, ll>>> g(n + 1);
for (int i = 0; i < n - 1; i++) { g[eu[i]].push_back({ev[i], ew[i]}); g[ev[i]].push_back({eu[i], ew[i]}); }
ll ans = 0;
vector<ll> S(n + 1), M(n + 1);
vector<int> par(n + 1);
for (int u = 1; u <= n; u++) {
vector<int> st = {u};
par[u] = 0; S[u] = 0; M[u] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x > u && 2 * M[x] < S[x]) ans++;
for (auto [y, ww] : g[x]) {
if (y == par[x]) continue;
par[y] = x; S[y] = S[x] + ww; M[y] = max(M[x], ww);
st.push_back(y);
}
}
}
return ans;
}
ll equalWeights() { // Cach 2: moi doan bang nhau
vector<ll> deg(n + 1, 0);
for (int i = 0; i < n - 1; i++) { deg[eu[i]]++; deg[ev[i]]++; }
ll ans = (ll)n * (n - 1) / 2 - (n - 1);
for (int v = 1; v <= n; v++) ans -= deg[v] * (deg[v] - 1) / 2;
return ans;
}
// dem so cap (x, y): s[y] <= t[x]
ll countPairs(vector<ll> s, vector<ll> t) {
sort(s.begin(), s.end());
sort(t.begin(), t.end());
ll res = 0;
size_t j = 0;
for (size_t i = 0; i < t.size(); i++) {
while (j < s.size() && s[j] <= t[i]) j++;
res += j;
}
return res;
}
void solve(int l, int r) { // Cach 3: dem so doan con [i..j] "xau" nam trong [l..r]
if (l == r) { bad++; return; } // 1 doan kenh: luon xau
int mid = (l + r) / 2;
solve(l, mid); solve(mid + 1, r);
vector<ll> Ls, Lt, Rs, Rt;
ll s = 0, m = 0;
for (int i = mid; i >= l; i--) { s += w[i]; m = max(m, w[i]); Ls.push_back(s); Lt.push_back(2 * m - s); }
s = 0; m = 0;
for (int j = mid + 1; j <= r; j++) { s += w[j]; m = max(m, w[j]); Rs.push_back(s); Rt.push_back(2 * m - s); }
bad += countPairs(Rs, Lt) + countPairs(Ls, Rt);
if (w[mid] == w[mid + 1]) bad--; // cap {w[mid]}, {w[mid+1]} bi dem 2 lan
}
int main() {
scanf("%d", &n);
eu.resize(n); ev.resize(n); ew.resize(n); w.assign(n + 1, 0);
bool same = true, path = true;
for (int i = 0; i < n - 1; i++) {
scanf("%d %d %lld", &eu[i], &ev[i], &ew[i]);
if (ew[i] != ew[0]) same = false;
if (min(eu[i], ev[i]) != i + 1 || max(eu[i], ev[i]) != i + 2) path = false;
else w[i + 1] = ew[i]; // canh noi i+1 va i+2
}
ll ans;
if (path) {
if (n >= 2) solve(1, n - 1);
ans = (ll)n * (n - 1) / 2 - bad;
} else if (same) ans = equalWeights();
else ans = brute();
printf("%lld\n", ans);
return 0;
}import sys
from bisect import bisect_right
from itertools import repeat
def brute(n, edges):
# Cach 1: duyet tu moi dinh, O(N^2)
g = [[] for _ in range(n + 1)]
for u, v, w in edges:
g[u].append((v, w)); g[v].append((u, w))
ans = 0
S = [0] * (n + 1); M = [0] * (n + 1); par = [0] * (n + 1)
for u in range(1, n + 1):
st = [u]; par[u] = 0; S[u] = 0; M[u] = 0
while st:
x = st.pop()
if x > u and 2 * M[x] < S[x]:
ans += 1
sx = S[x]; mx = M[x]; px = par[x]
for y, w in g[x]:
if y == px:
continue
par[y] = x; S[y] = sx + w; M[y] = mx if mx > w else w
st.append(y)
return ans
def equal_weights(n, edges):
# Cach 2: moi doan bang nhau
deg = [0] * (n + 1)
for u, v, w in edges:
deg[u] += 1; deg[v] += 1
ans = n * (n - 1) // 2 - (n - 1)
for d in deg:
ans -= d * (d - 1) // 2
return ans
def count_pairs(s, t):
# so cap (x, y): s[y] <= t[x]
s = sorted(s)
return sum(map(bisect_right, repeat(s), t))
def path_dc(n, w):
# Cach 3: chia de tri tren mang w[1..n-1] (dung ngan xep thay cho de quy)
bad = 0
stack = [(1, n - 1)] if n >= 2 else []
while stack:
l, r = stack.pop()
if l == r:
bad += 1; continue
mid = (l + r) // 2
stack.append((l, mid)); stack.append((mid + 1, r))
Ls = []; Lt = []; Rs = []; Rt = []
s = 0; m = 0
for i in range(mid, l - 1, -1):
s += w[i]
if w[i] > m: m = w[i]
Ls.append(s); Lt.append(2 * m - s)
s = 0; m = 0
for j in range(mid + 1, r + 1):
s += w[j]
if w[j] > m: m = w[j]
Rs.append(s); Rt.append(2 * m - s)
bad += count_pairs(Rs, Lt) + count_pairs(Ls, Rt)
if w[mid] == w[mid + 1]:
bad -= 1
return n * (n - 1) // 2 - bad
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
edges = [(int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])) for i in range(n - 1)]
same = all(e[2] == edges[0][2] for e in edges)
path = all(min(e[0], e[1]) == i + 1 and max(e[0], e[1]) == i + 2 for i, e in enumerate(edges))
if path:
w = [0] + [e[2] for e in edges]
print(path_dc(n, w))
elif same:
print(equal_weights(n, edges))
else:
print(brute(n, edges))
main()Cách 4Phân rã centroid – O(N log² N) · 100%
Chia để trị trên mảng chọn "điểm giữa"; trên cây, điểm giữa chính là trọng tâm (centroid) $c$: đỉnh mà khi xoá đi, mọi thành phần còn lại có không quá một nửa số đỉnh. Mọi tuyến trong thành phần hiện tại chia làm hai loại: đi qua $c$ (đếm ngay) và nằm trọn trong một nhánh (đệ quy sau khi xoá $c$). Vì mỗi lần kích thước giảm một nửa, mỗi đỉnh chỉ nằm trong $O(\log N)$ thành phần.
Tuyến $x \leftrightarrow y$ đi qua trọng tâm $c$ = nửa $c \to x$ ghép nửa $c \to y$, với $x, y$ ở hai nhánh khác nhau (hoặc một trong hai là chính $c$).
Với mỗi đỉnh $x$ của thành phần, tính $s_x$ = tổng, $m_x$ = max trên đường $c \to x$, và $t_x = 2m_x - s_x$. Bản thân $c$ có $s = m = t = 0$. Bổ đề nửa đường ở Cách 3 vẫn y nguyên, nên số tuyến xấu đi qua $c$ là
$$\underbrace{\#\{(x, y) \text{ khác nhánh}: s_y \le t_x\}}_{\text{cặp có thứ tự}} \;-\; \sum_{w} \binom{k_w}{2},$$
trong đó $k_w$ là số cạnh kề $c$ có chiều dài $w$ (các cặp "hai nửa cùng là một cạnh, bằng nhau" bị đếm 2 lần). Đếm cặp khác nhánh theo kiểu bù trừ: đếm trên toàn bộ danh sách, rồi trừ đi số đếm bên trong từng nhánh (chính $c$ là một "nhánh" riêng có 1 phần tử). Cặp $(x, x)$ được đếm khi $s_x \le t_x$, nhưng nó nằm cùng nhánh với chính nó nên tự triệt tiêu.
Hai mẹo tăng tốc trong code: $t_x < 0$ thì không có $s \ge 0$ nào $\le t_x$, bỏ luôn; và $s > \max t$ thì không bao giờ được đếm, cũng bỏ. Với trọng số ngẫu nhiên phần lớn các nửa đường dài đều có $t < 0$, nên số phần tử phải sắp xếp giảm mạnh.
Mô phỏng phân rã centroid (đỏ: trọng tâm đang xét, xanh: thành phần hiện tại, xám: đã xoá):
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> st, to, par, sz, order_; // ke cua u: to[st[u] .. st[u+1]-1]
vector<ll> wt, S, M;
vector<char> removed_;
// dem so cap co thu tu (x, y): s[y] <= t[x] (mang s, t bi sap xep/thu gon tai cho)
ll countPairs(ll* s, ll* t, int len) {
int lt = 0, ls = 0;
ll maxT = -1;
for (int i = 0; i < len; i++) // t < 0 thi khong co s >= 0 nao <= t: bo qua
if (t[i] >= 0) { t[lt++] = t[i]; maxT = max(maxT, t[i]); }
if (lt == 0) return 0;
for (int i = 0; i < len; i++) // s > maxT thi khong bao gio duoc dem: bo qua
if (s[i] <= maxT) s[ls++] = s[i];
sort(s, s + ls);
sort(t, t + lt);
ll res = 0;
int j = 0;
for (int i = 0; i < lt; i++) {
while (j < ls && s[j] <= t[i]) j++;
res += j;
}
return res;
}
int main() {
scanf("%d", &n);
vector<int> eu(n), ev(n); vector<ll> ew(n);
st.assign(n + 2, 0);
for (int i = 0; i < n - 1; i++) {
scanf("%d %d %lld", &eu[i], &ev[i], &ew[i]);
st[eu[i] + 1]++; st[ev[i] + 1]++;
}
for (int u = 1; u <= n + 1; u++) st[u] += st[u - 1];
to.assign(2 * n, 0); wt.assign(2 * n, 0);
vector<int> pos(st.begin(), st.end());
for (int i = 0; i < n - 1; i++) {
to[pos[eu[i]]] = ev[i]; wt[pos[eu[i]]++] = ew[i];
to[pos[ev[i]]] = eu[i]; wt[pos[ev[i]]++] = ew[i];
}
removed_.assign(n + 1, 0);
sz.assign(n + 1, 0); par.assign(n + 1, 0);
S.assign(n + 1, 0); M.assign(n + 1, 0);
vector<ll> as(n + 1), at(n + 1), gs(n + 1), gt(n + 1), cw;
ll bad = 0;
vector<int> stk = {1};
while (!stk.empty()) {
int root = stk.back(); stk.pop_back();
// 1) duyet thanh phan chua root (BFS), tinh kich thuoc cay con
order_.clear(); order_.push_back(root); par[root] = 0;
for (size_t i = 0; i < order_.size(); i++) {
int u = order_[i];
for (int e = st[u]; e < st[u + 1]; e++) {
int v = to[e];
if (v != par[u] && !removed_[v]) { par[v] = u; order_.push_back(v); }
}
}
int tot = order_.size();
for (int i = tot - 1; i >= 0; i--) {
int u = order_[i]; sz[u] = 1;
for (int e = st[u]; e < st[u + 1]; e++) {
int v = to[e];
if (v != par[u] && !removed_[v]) sz[u] += sz[v];
}
}
// 2) tim trong tam c: di ve phia nhanh con co hon nua so dinh
int c = root;
while (true) {
int go = -1;
for (int e = st[c]; e < st[c + 1]; e++) {
int v = to[e];
if (v != par[c] && !removed_[v] && sz[v] * 2 > tot) { go = v; break; }
}
if (go == -1) break;
c = go;
}
// 3) moi dinh x trong thanh phan: S[x] = tong, M[x] = max tren duong c -> x
int cnt = 0;
as[cnt] = 0; at[cnt] = 0; cnt++; // chinh dinh c: S = 0, M = 0
ll inGroup = 1; // cap (c, c) cua nhom {c}
cw.clear(); // trong so cac canh ke c
for (int e = st[c]; e < st[c + 1]; e++) {
int v = to[e];
if (removed_[v]) continue;
cw.push_back(wt[e]);
order_.clear(); order_.push_back(v);
par[v] = c; S[v] = wt[e]; M[v] = wt[e];
for (size_t i = 0; i < order_.size(); i++) {
int u = order_[i];
for (int f = st[u]; f < st[u + 1]; f++) {
int x = to[f];
if (x != par[u] && !removed_[x]) {
par[x] = u; S[x] = S[u] + wt[f]; M[x] = max(M[u], wt[f]);
order_.push_back(x);
}
}
}
int g = order_.size();
for (int i = 0; i < g; i++) {
int u = order_[i];
gs[i] = as[cnt] = S[u];
gt[i] = at[cnt] = 2 * M[u] - S[u];
cnt++;
}
inGroup += countPairs(gs.data(), gt.data(), g); // cap cung nhanh: phai tru di
}
ll cross = countPairs(as.data(), at.data(), cnt) - inGroup;
sort(cw.begin(), cw.end()); // cap 2 canh ke c bang nhau: bi dem 2 lan
for (size_t i = 0, j; i < cw.size(); i = j) {
j = i;
while (j < cw.size() && cw[j] == cw[i]) j++;
ll k = j - i;
cross -= k * (k - 1) / 2;
}
bad += cross;
// 4) xoa c, xu ly tiep cac thanh phan con
removed_[c] = 1;
for (int e = st[c]; e < st[c + 1]; e++)
if (!removed_[to[e]]) stk.push_back(to[e]);
}
ll total = (ll)n * (n - 1) / 2;
printf("%lld\n", total - bad);
return 0;
}import sys
def count_pairs(s, t):
# so cap co thu tu (x, y): s[y] <= t[x] (hai con tro tren hai day da sap xep)
t = [v for v in t if v >= 0] # t < 0: khong co s >= 0 nao <= t
if not t:
return 0
mx = max(t)
s = [v for v in s if v <= mx] # s > max(t): khong bao gio duoc dem
s.sort(); t.sort()
res = 0; j = 0; ls = len(s)
for v in t:
while j < ls and s[j] <= v:
j += 1
res += j
return res
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
# danh sach ke dang mang phang: canh e di toi to[e], dai wt[e]; head/nxt
head = [-1] * (n + 1)
nxt = [0] * (2 * n); to = [0] * (2 * n); wt = [0] * (2 * n)
e = 0; p = 1
for _ in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
to[e] = v; wt[e] = w; nxt[e] = head[u]; head[u] = e; e += 1
to[e] = u; wt[e] = w; nxt[e] = head[v]; head[v] = e; e += 1
removed = [False] * (n + 1)
sz = [0] * (n + 1); par = [0] * (n + 1)
S = [0] * (n + 1); M = [0] * (n + 1)
bad = 0
stk = [1]
while stk:
root = stk.pop()
# 1) duyet thanh phan chua root (BFS), tinh kich thuoc cay con
order = [root]; par[root] = 0
i = 0
while i < len(order):
u = order[i]; i += 1
pu = par[u]; ed = head[u]
while ed != -1:
v = to[ed]
if v != pu and not removed[v]:
par[v] = u; order.append(v)
ed = nxt[ed]
tot = len(order)
for u in order:
sz[u] = 1
for k in range(tot - 1, 0, -1):
u = order[k]; sz[par[u]] += sz[u]
# 2) tim trong tam c: di ve phia nhanh con co hon nua so dinh
c = root; half = tot // 2
while True:
go = -1; ed = head[c]; pc = par[c]
while ed != -1:
v = to[ed]
if v != pc and not removed[v] and sz[v] > half:
go = v; break
ed = nxt[ed]
if go == -1:
break
c = go
# 3) moi dinh x: S[x] = tong, M[x] = max tren duong c -> x
allS = [0]; allT = [0] # chinh dinh c: S = 0, M = 0
in_group = 1 # cap (c, c) cua nhom {c}
cw = {} # dem trong so cac canh ke c
ed0 = head[c]
while ed0 != -1:
v = to[ed0]; w0 = wt[ed0]; ed0 = nxt[ed0]
if removed[v]:
continue
cw[w0] = cw.get(w0, 0) + 1
q = [v]; par[v] = c; S[v] = w0; M[v] = w0
i = 0
while i < len(q):
u = q[i]; i += 1
su = S[u]; mu = M[u]; pu = par[u]; ed = head[u]
while ed != -1:
x = to[ed]
if x != pu and not removed[x]:
wf = wt[ed]
par[x] = u
S[x] = su + wf
M[x] = mu if mu > wf else wf
q.append(x)
ed = nxt[ed]
gs = [S[u] for u in q]
gt = [2 * M[u] - S[u] for u in q]
allS += gs; allT += gt
in_group += count_pairs(gs, gt) # cap cung nhanh: phai tru di
cross = count_pairs(allS, allT) - in_group
for k in cw.values(): # cap 2 canh ke c bang nhau: bi dem 2 lan
cross -= k * (k - 1) // 2
bad += cross
# 4) xoa c, xu ly tiep cac thanh phan con
removed[c] = True
ed = head[c]
while ed != -1:
v = to[ed]
if not removed[v]:
stk.append(v)
ed = nxt[ed]
print(n * (n - 1) // 2 - bad)
main()wrong_khongcentroid.cpp qua hết subtask 1, một phần subtask 2, 4 nhưng TLE toàn bộ subtask 3.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 31 test: subtask 1 (8 test, $N \le 2000$), subtask 2 (6 test, $N \approx 2\cdot 10^5$, mọi đoạn bằng nhau), subtask 3 (7 test, đường thẳng $N \approx 2\cdot 10^5$), subtask 4 (10 test, $N \approx 2\cdot 10^5$: cây ngẫu nhiên, gần như thẳng, sâu rơm, hình sao, chổi, nhị phân, vài "chợ nổi" lớn). Trọng số được sinh đủ kiểu: ngẫu nhiên tới $10^9$, chỉ $1..3$ (rất nhiều dấu bằng $2D = L$), lũy thừa của 2 giảm dần theo độ sâu (đoạn trên cùng "áp đảo"), vài đoạn khổng lồ xen giữa các đoạn rất ngắn.
| Cách làm | Sub 1 (15%) | Sub 2 (20%) | Sub 3 (25%) | Sub 4 (40%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Duyệt từ mọi bến O(N²) | Đúng | TLE | TLE | TLE | 15 |
| Cách 2 – Cách 1 + công thức khi mọi đoạn bằng nhau | Đúng | Đúng | TLE | TLE | 35 |
| Cách 3 – Cách 2 + chia để trị trên đường thẳng | Đúng | Đúng | Đúng | TLE | 60 |
| Cách 4 – Phân rã centroid (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: coi 2D ≤ L là cân bằng | WA | WA | WA | WA | 0 |
| Sai: quên trừ cặp bị đếm 2 lần | 3/8 (WA) | WA | 2/7 (WA) | 1/10 (WA) | 16,8 |
| Sai: tổng độ dài dùng int | 5/8 (WA) | 5/6 (WA) | 3/7 (WA) | 5/10 (WA) | 56,8 |
| Sai: không tìm trọng tâm (lấy đỉnh bất kỳ) | Đúng | 4/6 (TLE) | TLE | 5/10 (TLE) | 48,3 |
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: sub1.cpp được 15 điểm; sub2.cpp được 35 điểm; sub3.cpp được 60 điểm; sol.cpp được 100 điểm; wrong_lebang.cpp được 0 điểm; wrong_quentrung.cpp được 16,8 điểm; wrong_tranint.cpp được 56,8 điểm; wrong_khongcentroid.cpp được 48,3 điểm. Lời giải chuẩn sol.cpp chạy test lâu nhất hết 0,6 giây, bản Python sol.py cho cùng đáp án trên mọi test (trên CPython chạy chậm hơn đáng kể, các em nhớ chọn PyPy 3 khi nộp). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian.
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