Thăm xóm (Đề tự luyện HSG Tin quốc gia – Bài 1)
Đề bài
Thăm xóm
Có $N$ xóm nối với nhau bởi $N - 1$ con kênh thành một cây. Con kênh thứ $j$ nối xóm $u_j, v_j$ với phí $w_j$; xóm $i$ có phí ghé $c_i$. Giá chuyến đò từ xóm $u$ tới xóm $v$ ($u \ne v$) là tổng phí các con kênh trên đường đi duy nhất giữa hai xóm cộng tổng phí ghé của mọi xóm trên đường (kể cả hai đầu).
Đếm số cặp $\{u, v\}$ ($u < v$) có giá chuyến đò chia hết cho $K$.
Dữ liệu vào: dòng đầu $N, K$ ($1 \le N \le 10^5$; $1 \le K \le 50$); dòng hai $c_1, \ldots, c_N$ ($1 \le c_i \le 10^9$); $N - 1$ dòng tiếp theo mỗi dòng $u_j\ v_j\ w_j$ ($1 \le w_j \le 10^9$).
Kết quả: số cặp xóm thỏa mãn.
- Subtask 1 (15%): $N \le 2000$.
- Subtask 2 (15%): mọi con kênh đều có một đầu là xóm $1$.
- Subtask 3 (25%): con kênh thứ $j$ nối xóm $j$ và xóm $j + 1$.
- Subtask 4 (45%): không có ràng buộc gì thêm.
7 5
4 4 8 2 6 4 4
1 2 6
2 3 3
1 4 6
3 5 3
4 6 5
5 7 44Bốn cặp thỏa mãn: $\{1, 3\}$ (giá $25$), $\{2, 3\}$ (giá $15$), $\{3, 7\}$ (giá $25$), $\{4, 7\}$ (giá $50$). Mọi cặp khác có giá không chia hết cho $5$.
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 Thăm xómLời mở đầu
Có $\frac{N(N-1)}{2}$ cặp xóm – với $N = 10^5$ là khoảng $5 \cdot 10^9$ cặp, không thể xét từng cặp. Hai nhận xét giúp ta đếm "theo nhóm":
- Chỉ cần số dư. Ta chỉ quan tâm giá chia $K$ dư bao nhiêu, nên mọi $c_i, w_j$ có thể lấy $\bmod K$ ngay từ đầu. Với $K \le 50$, mỗi "tổng" chỉ có tối đa $50$ giá trị.
- Mỗi đường đi có một điểm cao nhất. Treo cây tại xóm $1$. Đường đi giữa $x$ và $y$ đi lên tới xóm $u$ – tổ tiên chung thấp nhất – rồi đi xuống. Gọi $\text{down}(u \to x)$ là tổng phí từ $u$ đi xuống tới $x$ (gồm các con kênh và phí ghé các xóm trên đường, không tính $c_u$). Khi đó $$\text{giá}(x, y) = c_u + \text{down}(u \to x) + \text{down}(u \to y).$$ Phí của xóm $u$ chỉ được cộng một lần. (Nếu $x = u$ thì $\text{down}(u \to u) = 0$.)
Mọi cặp được đếm đúng một lần, tại xóm cao nhất của đường đi giữa chúng.
Ví dụ: cặp $\{4, 7\}$ có điểm cao nhất là xóm $1$; $\text{down}(1 \to 4) = 6 + 2 = 8$, $\text{down}(1 \to 7) = 6 + 4 + 3 + 8 + 3 + 6 + 4 + 4 = 38$, giá $= 4 + 8 + 38 = 50$.
Cách 1Xuất phát từ từng xóm – O(N²) · 15%
Với mỗi xóm $u$, duyệt cây (DFS bằng ngăn xếp) bắt đầu với $tot[u] = c_u$; đi sang xóm $y$ qua con kênh phí $w$ thì $tot[y] = tot[x] + w + c_y$ (lấy mod $K$). Đếm các xóm $x > u$ có $tot[x] = 0$ – điều kiện $x > u$ để mỗi cặp chỉ đếm một lần. Mỗi lần duyệt $O(N)$, tổng $O(N^2) = 4 \cdot 10^6$ phép tính khi $N \le 2000$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, K;
cin >> n >> K;
vector<long long> c(n + 1);
for (int i = 1; i <= n; i++) { cin >> c[i]; c[i] %= K; }
vector<vector<pair<int,int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v; long long w;
cin >> u >> v >> w;
g[u].push_back({v, (int)(w % K)});
g[v].push_back({u, (int)(w % K)});
}
long long ans = 0;
vector<int> tot(n + 1), par(n + 1);
for (int u = 1; u <= n; u++) { // xuat phat tu xom u, di toi moi xom
vector<int> st = {u};
tot[u] = c[u]; par[u] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x > u && tot[x] == 0) ans++; // moi cap (u, x) chi dem mot lan
for (auto [y, w] : g[x]) if (y != par[x]) {
par[y] = x;
tot[y] = (tot[x] + w + c[y]) % K;
st.push_back(y);
}
}
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
c = [0] * (n + 1)
for i in range(1, n + 1): c[i] = int(data[1 + i]) % K
g = [[] for _ in range(n + 1)]
p = n + 2
for i in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]) % K; p += 3
g[u].append((v, w)); g[v].append((u, w))
ans = 0
tot = [0] * (n + 1); par = [0] * (n + 1)
for u in range(1, n + 1): # xuat phat tu xom u, di toi moi xom
st = [u]; tot[u] = c[u]; par[u] = 0
while st:
x = st.pop()
if x > u and tot[x] == 0: ans += 1 # moi cap (u, x) chi dem mot lan
for y, w in g[x]:
if y != par[x]:
par[y] = x
tot[y] = (tot[x] + w + c[y]) % K
st.append(y)
print(ans)
main()Cách 2Cây hình sao – đếm cặp theo số dư O(N + K) · 30%
Khi mọi con kênh đều chạm xóm $1$, mỗi xóm lá $x$ có $a_x = (w_x + c_x) \bmod K$. Có hai loại cặp:
- $\{1, x\}$: giá $c_1 + a_x$.
- $\{x, y\}$ (hai xóm lá): giá $c_1 + a_x + a_y$ – điểm cao nhất là xóm $1$.
Duyệt lần lượt các xóm lá, giữ mảng $cnt[r]$ = số xóm lá đã xét có $a = r$. Với xóm lá $x$ mới, số bạn ghép được với nó là $cnt[(-c_1 - a_x) \bmod K]$. Đây là kỹ thuật "đếm cặp có tổng chia hết cho $K$" quen thuộc – và cũng chính là phép ghép ta sẽ dùng ở Cách 4.
Lưu ý: số cặp có thể tới khoảng $5 \cdot 10^9$, phải dùng long long!
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, K;
cin >> n >> K;
vector<long long> c(n + 1);
for (int i = 1; i <= n; i++) { cin >> c[i]; c[i] %= K; }
vector<vector<pair<int,int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v; long long w;
cin >> u >> v >> w;
g[u].push_back({v, (int)(w % K)});
g[v].push_back({u, (int)(w % K)});
}
bool star = true; // Cach 2: moi con duong deu co mot dau la xom 1
for (int x = 2; x <= n; x++) if (g[x].size() != 1 || g[x][0].first != 1) star = false;
if (star) {
vector<long long> cnt(K, 0); // cnt[r]: so xom la x da xet co (w + c[x]) mod K = r
long long ans = 0;
for (auto [x, w] : g[1]) {
int a = (w + c[x]) % K;
if ((c[1] + a) % K == 0) ans++; // cap (1, x)
ans += cnt[((K - c[1] - a) % K + K) % K]; // cap (y, x) voi y la xom la truoc do
cnt[a]++;
}
cout << ans << "\n";
return 0;
}
long long ans = 0; // con lai: Cach 1
vector<int> tot(n + 1), par(n + 1);
for (int u = 1; u <= n; u++) { // xuat phat tu xom u, di toi moi xom
vector<int> st = {u};
tot[u] = c[u]; par[u] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x > u && tot[x] == 0) ans++; // moi cap (u, x) chi dem mot lan
for (auto [y, w] : g[x]) if (y != par[x]) {
par[y] = x;
tot[y] = (tot[x] + w + c[y]) % K;
st.push_back(y);
}
}
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
c = [0] * (n + 1)
for i in range(1, n + 1): c[i] = int(data[1 + i]) % K
g = [[] for _ in range(n + 1)]
p = n + 2
for i in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]) % K; p += 3
g[u].append((v, w)); g[v].append((u, w))
star = all(len(g[x]) == 1 and g[x][0][0] == 1 for x in range(2, n + 1))
if star: # Cach 2: moi con duong deu co mot dau la xom 1
cnt = [0] * K # cnt[r]: so xom la da xet co (w + c[x]) mod K = r
ans = 0
for x, w in g[1]:
a = (w + c[x]) % K
if (c[1] + a) % K == 0: ans += 1 # cap (1, x)
ans += cnt[(-c[1] - a) % K] # cap (y, x), y la xom la truoc do
cnt[a] += 1
print(ans); return
ans = 0 # con lai: Cach 1
tot = [0] * (n + 1); par = [0] * (n + 1)
for u in range(1, n + 1): # xuat phat tu xom u, di toi moi xom
st = [u]; tot[u] = c[u]; par[u] = 0
while st:
x = st.pop()
if x > u and tot[x] == 0: ans += 1 # moi cap (u, x) chi dem mot lan
for y, w in g[x]:
if y != par[x]:
par[y] = x
tot[y] = (tot[x] + w + c[y]) % K
st.append(y)
print(ans)
main()Cách 3Các xóm nằm trên một đường thẳng – tiền tố theo modulo O(N + K) · 55%
Khi con kênh thứ $j$ nối xóm $j$ và $j + 1$, giá chuyến từ $u$ tới $v$ ($u < v$) là $\sum_{j=u}^{v-1} w_j + \sum_{i=u}^{v} c_i$. Đặt $W_v = w_1 + \dots + w_{v-1}$ và $C_v = c_1 + \dots + c_v$, ta có $$\text{giá}(u, v) = \underbrace{(W_v + C_v)}_{X_v} - \underbrace{(W_u + C_{u-1})}_{Y_u}.$$ Giá chia hết cho $K$ $\iff X_v \equiv Y_u \pmod K$. Duyệt $v$ từ $1$ tới $N$: cộng vào đáp án số $u < v$ đã có $Y_u \equiv X_v$ (đếm bằng mảng $cnt$), rồi thêm $Y_v$ vào $cnt$.
Chạy tay một đường thẳng nhỏ: $N = 4$, $K = 3$, $c = (1, 2, 1, 2)$, $w = (1, 1, 2)$.
| $v$ | $X_v = W_v + C_v$ | $Y_v = W_v + C_{v-1}$ | Cặp mới |
|---|---|---|---|
| 1 | 0 + 1 = 1 | 0 + 0 = 0 | – |
| 2 | 1 + 3 = 4 ≡ 1 | 1 + 1 = 2 | không có $Y_u \equiv 1$ |
| 3 | 2 + 4 = 6 ≡ 0 | 2 + 3 = 5 ≡ 2 | $u = 1$ ($Y_1 = 0$): giá $1+1+2+1+1 = 6$ |
| 4 | 4 + 6 = 10 ≡ 1 | 4 + 4 = 8 ≡ 2 | không có $Y_u \equiv 1$ |
Đáp án là $1$. Code dưới đây giữ lại Cách 2 và Cách 1 cho các dạng cây khác.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, K;
cin >> n >> K;
vector<long long> c(n + 1);
for (int i = 1; i <= n; i++) { cin >> c[i]; c[i] %= K; }
vector<vector<pair<int,int>>> g(n + 1);
vector<int> eu(n), ev(n), ew(n);
for (int i = 0; i < n - 1; i++) {
int u, v; long long w;
cin >> u >> v >> w;
eu[i] = u; ev[i] = v; ew[i] = w % K;
g[u].push_back({v, (int)(w % K)});
g[v].push_back({u, (int)(w % K)});
}
bool path = true; // Cach 3: con duong thu i noi xom i va xom i + 1
vector<long long> wp(n + 1, 0);
for (int i = 0; i < n - 1; i++) if (abs(eu[i] - ev[i]) != 1) path = false; else wp[min(eu[i], ev[i])] = ew[i];
if (path) {
// tong(u..v) = X[v] - Y[u] voi X[v] = W[v] + C[v], Y[u] = W[u] + C[u - 1]
vector<long long> cnt(K, 0);
long long ans = 0, W = 0, C = 0; // W = w[1] + ... + w[v-1], C = c[1] + ... + c[v]
for (int v = 1; v <= n; v++) {
long long Cprev = C;
C = (C + c[v]) % K;
ans += cnt[(W + C) % K]; // cac u < v co Y[u] = X[v]
cnt[(W + Cprev) % K]++; // them Y[v]
W = (W + wp[v]) % K;
}
cout << ans << "\n";
return 0;
}
bool star = true; // Cach 2: moi con duong deu co mot dau la xom 1
for (int x = 2; x <= n; x++) if (g[x].size() != 1 || g[x][0].first != 1) star = false;
if (star) {
vector<long long> cnt(K, 0); // cnt[r]: so xom la x da xet co (w + c[x]) mod K = r
long long ans = 0;
for (auto [x, w] : g[1]) {
int a = (w + c[x]) % K;
if ((c[1] + a) % K == 0) ans++; // cap (1, x)
ans += cnt[((K - c[1] - a) % K + K) % K]; // cap (y, x) voi y la xom la truoc do
cnt[a]++;
}
cout << ans << "\n";
return 0;
}
long long ans = 0; // con lai: Cach 1
vector<int> tot(n + 1), par(n + 1);
for (int u = 1; u <= n; u++) { // xuat phat tu xom u, di toi moi xom
vector<int> st = {u};
tot[u] = c[u]; par[u] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x > u && tot[x] == 0) ans++; // moi cap (u, x) chi dem mot lan
for (auto [y, w] : g[x]) if (y != par[x]) {
par[y] = x;
tot[y] = (tot[x] + w + c[y]) % K;
st.push_back(y);
}
}
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
c = [0] * (n + 1)
for i in range(1, n + 1): c[i] = int(data[1 + i]) % K
g = [[] for _ in range(n + 1)]
p = n + 2
eu = [0] * n; ev = [0] * n; ew = [0] * n
for i in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]) % K; p += 3
eu[i] = u; ev[i] = v; ew[i] = w
g[u].append((v, w)); g[v].append((u, w))
path = all(abs(eu[i] - ev[i]) == 1 for i in range(n - 1))
if path: # Cach 3: con duong thu i noi xom i va xom i + 1
wp = [0] * (n + 1)
for i in range(n - 1): wp[min(eu[i], ev[i])] = ew[i]
cnt = [0] * K # tong(u..v) = X[v] - Y[u]
ans = 0; W = 0; C = 0
for v in range(1, n + 1):
Cprev = C
C = (C + c[v]) % K
ans += cnt[(W + C) % K] # cac u < v co Y[u] = X[v]
cnt[(W + Cprev) % K] += 1 # them Y[v]
W = (W + wp[v]) % K
print(ans); return
star = all(len(g[x]) == 1 and g[x][0][0] == 1 for x in range(2, n + 1))
if star: # Cach 2: moi con duong deu co mot dau la xom 1
cnt = [0] * K # cnt[r]: so xom la da xet co (w + c[x]) mod K = r
ans = 0
for x, w in g[1]:
a = (w + c[x]) % K
if (c[1] + a) % K == 0: ans += 1 # cap (1, x)
ans += cnt[(-c[1] - a) % K] # cap (y, x), y la xom la truoc do
cnt[a] += 1
print(ans); return
ans = 0 # con lai: Cach 1
tot = [0] * (n + 1); par = [0] * (n + 1)
for u in range(1, n + 1): # xuat phat tu xom u, di toi moi xom
st = [u]; tot[u] = c[u]; par[u] = 0
while st:
x = st.pop()
if x > u and tot[x] == 0: ans += 1 # moi cap (u, x) chi dem mot lan
for y, w in g[x]:
if y != par[x]:
par[y] = x
tot[y] = (tot[x] + w + c[y]) % K
st.append(y)
print(ans)
main()Cách 4QHĐ trên cây theo số dư – O(N · K) · 100%
Kết hợp hai ý ở trên. Với mỗi xóm $u$, gọi $A_u[r]$ là số xóm $x$ trong cây con gốc $u$ (kể cả chính $u$) có $\text{down}(u \to x) \equiv r \pmod K$. Ban đầu $A_u = [1, 0, \ldots, 0]$ (chỉ có $u$ với tổng $0$). Lần lượt ghép từng con $v$ (con kênh $u$–$v$ phí $w$) vào $u$:
- Dịch mảng của con: đi từ $u$ xuống $v$ tốn thêm $s = w + c_v$, nên $B[(r + s) \bmod K] = A_v[r]$ – $B$ là mảng của cây con $v$ nhưng "nhìn từ $u$".
- Đếm cặp có điểm cao nhất là $u$: một xóm $x$ ở phần đã ghép (gồm $u$ và các cây con trước) với một xóm $y$ trong cây con $v$. Cần $c_u + a + b \equiv 0$, tức $a + b \equiv t$ với $t = (-c_u) \bmod K$: $$ans \mathrel{+}= \sum_{r=0}^{K-1} A_u[r] \cdot B[(t - r) \bmod K].$$
- Gộp: $A_u[r] \mathrel{+}= B[r]$ với mọi $r$.
Vì $x$ và $y$ nằm ở hai nhánh khác nhau (hoặc $x = u$), điểm cao nhất của đường đi giữa chúng đúng là $u$ – mỗi cặp được đếm đúng một lần. Để khỏi đệ quy sâu (cây có thể là đường dài $10^5$), ta lấy thứ tự BFS từ xóm $1$ và xử lý theo thứ tự ngược lại: mọi con được xử lý xong trước cha. Mảng của con được giải phóng ngay sau khi ghép.
Các em thử nhập một cây nhỏ để xem từng bước ghép nhé (mỗi con kênh là u v w, cách nhau bằng dấu chấm phẩy):
Mỗi con kênh tốn $O(K)$ phép tính nên tổng là $O(NK) \le 5 \cdot 10^6$. Bản Python dùng các phép cắt/ghép danh sách và map (chạy ở tầng C) để dịch mảng và tính tổng tích cho nhanh.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, K;
cin >> n >> K;
vector<long long> c(n + 1);
for (int i = 1; i <= n; i++) { cin >> c[i]; c[i] %= K; }
vector<vector<pair<int,int>>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v; long long w;
cin >> u >> v >> w;
g[u].push_back({v, (int)(w % K)});
g[v].push_back({u, (int)(w % K)});
}
// thu tu BFS tu xom 1; xu ly nguoc lai de con xong truoc cha
vector<int> order = {1}, par(n + 1, 0), pw(n + 1, 0);
par[1] = -1;
for (int i = 0; i < (int)order.size(); i++) {
int u = order[i];
for (auto [v, w] : g[u]) if (v != par[u]) { par[v] = u; pw[v] = w; order.push_back(v); }
}
// A[u][r]: so xom x trong cay con goc u co tong (tu u xuong x, khong tinh c[u]) chia K du r
vector<vector<int>> A(n + 1);
long long ans = 0;
for (int i = n - 1; i >= 0; i--) {
int v = order[i];
if (A[v].empty()) { A[v].assign(K, 0); A[v][0] = 1; } // xom la
int u = par[v];
if (u < 0) break;
if (A[u].empty()) { A[u].assign(K, 0); A[u][0] = 1; } // chi co chinh u
int s = (pw[v] + c[v]) % K; // di tu u xuong v
vector<int> B(K);
for (int r = 0; r < K; r++) B[(r + s) % K] = A[v][r];
int t = (K - c[u]) % K; // can: c[u] + a + b chia het cho K
for (int r = 0; r < K; r++) ans += (long long)A[u][r] * B[(t - r + K) % K];
for (int r = 0; r < K; r++) A[u][r] += B[r];
vector<int>().swap(A[v]); // giai phong
}
cout << ans << "\n";
return 0;
}import sys
from operator import mul, add
def main():
data = sys.stdin.buffer.read().split()
n, K = int(data[0]), int(data[1])
c = [0] * (n + 1)
for i in range(1, n + 1): c[i] = int(data[1 + i]) % K
g = [[] for _ in range(n + 1)] # luu v * K + (w mod K)
p = n + 2
for i in range(n - 1):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]) % K; p += 3
g[u].append(v * K + w); g[v].append(u * K + w)
# thu tu BFS tu xom 1; xu ly nguoc lai de con xong truoc cha
order = [1]; par = [0] * (n + 1); pw = [0] * (n + 1); par[1] = -1
for u in order:
pu = par[u]
for x in g[u]:
v = x // K
if v != pu:
par[v] = u; pw[v] = x - v * K; order.append(v)
A = [None] * (n + 1) # A[u][r]: so xom x trong cay con u co tong (u -> x, khong tinh c[u]) du r
base = [1] + [0] * (K - 1)
ans = 0
for i in range(n - 1, 0, -1):
v = order[i]; u = par[v]
Av = A[v]
if Av is None: Av = base # xom la
Au = A[u]
if Au is None: Au = base
s = (pw[v] + c[v]) % K # di tu u xuong v
B = Av[-s:] + Av[:-s] if s else Av # B[r] = Av[(r - s) mod K]
t = (K - c[u]) % K # can: c[u] + a + b chia het cho K
q = (K - 1 - t) % K
R = B[::-1]; R = R[q:] + R[:q] # R[r] = B[(t - r) mod K]
ans += sum(map(mul, Au, R))
A[u] = list(map(add, Au, B))
A[v] = None # giai phong
sys.stdout.write(str(ans) + "\n")
main()int – đáp án có thể lên tới gần $5 \cdot 10^9$.Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 (15%) | Sub 2 (15%) | Sub 3 (25%) | Sub 4 (45%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – DFS từ từng xóm O(N²) | Đúng | TLE | TLE | TLE | 15 |
| Cách 2 – Hình sao: đếm theo số dư | Đúng | Đúng | TLE | TLE | 30 |
| Cách 3 – Đường thẳng: tiền tố mod K | Đúng | Đúng | Đúng | TLE | 55 |
| Cách 4 – QHĐ trên cây theo số dư (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
Sai: đúng ý tưởng nhưng đáp án kiểu int | 8/8 | 4/8 | 5/8 | 6/10 | 65,1 |
| Sai: quên phí ghé của xóm cao nhất trên đường đi | 2/8 | 3/8 | 3/8 | 2/10 | 27,8 |
| Sai: đếm cả "chuyến" từ một xóm tới chính nó | 2/8 | 0/8 | 0/8 | 0/10 | 3,8 |
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: bộ test có 34 test (8 + 8 + 8 + 10), mỗi cách đạt đúng số điểm công bố, còn ba lời giải sai bị bắt như bảng trên. Lời giải chuẩn sol.cpp chạy test lâu nhất chỉ khoảng 0,1 giây; bản Python sol.py cho cùng đáp án trên mọi test (trên CPython chưa tới 1 giây, các em vẫn nên chọn PyPy 3 khi nộp). Cách 1 – 3 khi gặp cây không đúng dạng của mình phải quay về duyệt $O(N^2)$ với $N = 10^5$ nên chạy quá 4 giây mỗi test. "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian. Lỗi để đáp án kiểu int chỉ lộ khi số cặp vượt khoảng $2{,}1 \cdot 10^9$ (khi $K$ nhỏ hoặc phần lớn các phí chia hết cho $K$), nên nó vẫn "ăn" trọn subtask 1 – đừng để mất điểm oan như vậy nhé!
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