Lều trại (Đề tự luyện HSG Tin quốc gia – Bài 2)
Đề bài
Lều trại
Có $N$ chi đội, mỗi chi đội dựng trại ở bờ Đông (D) hoặc bờ Tây (T) của con kênh. Có $M$ nguyện vọng, nguyện vọng thứ $j$ là "chi đội $a_j$ ở bờ $X_j$ hoặc chi đội $b_j$ ở bờ $Y_j$" (cần ít nhất một điều đúng, có thể $a_j = b_j$). Một cách xếp là hợp lệ nếu đáp ứng mọi nguyện vọng.
Với mỗi chi đội $i$: in D nếu mọi cách xếp hợp lệ đều đặt nó ở bờ Đông, T nếu mọi cách xếp hợp lệ đều đặt nó ở bờ Tây, ? nếu còn tự do. Nếu không có cách xếp hợp lệ nào thì in $-1$.
Dữ liệu vào: dòng đầu $N, M$ ($1 \le N \le 5 \cdot 10^4$; $1 \le M \le 10^5$); $M$ dòng tiếp theo dạng a X b Y.
Kết quả: một xâu $N$ ký tự, hoặc $-1$.
- Subtask 1 (15%): $N \le 15$ và $M \le 50$.
- Subtask 2 (20%): $N \le 2000$ và $M \le 5000$.
- Subtask 3 (25%): $|a_j - b_j| \le 1$ với mọi $j$.
- Subtask 4 (40%): không có ràng buộc gì thêm.
8 8
1 D 1 D
1 T 3 D
3 T 5 T
5 D 2 D
4 D 6 T
6 D 7 D
7 T 4 T
8 D 2 TDDD?T??DChỉ có hai cách xếp hợp lệ: DDDDTDTD và DDDTTTDD. Các chi đội $1, 2, 3, 8$ luôn ở bờ Đông, chi đội $5$ luôn ở bờ Tây, còn các chi đội $4, 6, 7$ còn tự do.
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 Lều trạiLời mở đầu
Mỗi chi đội chỉ có hai lựa chọn, mỗi nguyện vọng là "điều này hoặc điều kia" – đây đúng là dạng bài 2-SAT. Ta đặt $2N$ "mệnh đề": $D_i$ = "chi đội $i$ ở bờ Đông", $T_i$ = "chi đội $i$ ở bờ Tây"; hai mệnh đề này là phủ định của nhau ($\neg D_i = T_i$).
Nguyện vọng "$p$ hoặc $q$" tương đương với hai phép kéo theo: "nếu không $p$ thì $q$" và "nếu không $q$ thì $p$". Vẽ mỗi phép kéo theo thành một cung có hướng, ta được đồ thị kéo theo $2N$ đỉnh, $2M$ cung. Ví dụ nguyện vọng "đội 1 ở Tây hoặc đội 3 ở Đông" cho hai cung $D_1 \to D_3$ và $T_3 \to T_1$.
Một phần đồ thị kéo theo của ví dụ (nv = nguyện vọng). Từ $T_1$ đi được tới $D_1$: chi đội 1 không thể ở bờ Tây. Kéo theo dây chuyền, $D_3$, $T_5$, $D_2$ cũng luôn đúng.
Kiến thức 2-SAT kinh điển: có cách xếp hợp lệ khi và chỉ khi không có chi đội $i$ nào mà $D_i$ và $T_i$ nằm cùng một thành phần liên thông mạnh. Bài này hỏi sâu hơn một bước: chi đội nào bị ép? Đây là nhận xét quan trọng nhất của bài:
Chứng minh. Chiều $(\Leftarrow)$: nếu một cách xếp hợp lệ đặt $i$ ở bờ Tây thì $T_i$ đúng, đi theo các cung kéo theo mọi mệnh đề trên đường đều đúng, nên $D_i$ cũng đúng – vô lý. Chiều $(\Rightarrow)$: ta dùng một sự thật quen thuộc của 2-SAT – với bất kỳ thứ tự topo nào của đồ thị các thành phần liên thông mạnh, nếu gán mỗi mệnh đề là "đúng" khi thành phần của nó đứng sau thành phần của phủ định của nó, ta luôn được một cách xếp hợp lệ. (Thật vậy, xét cung $x \to y$ với $x$ đúng: cung phản đảo $\neg y \to \neg x$ cho thứ tự $\neg y$ trước $\neg x$, mà $\neg x$ trước $x$, $x$ trước $y$, nên $\neg y$ trước $y$, tức $y$ cũng đúng; vì vậy không nguyện vọng nào có cả hai vế sai.) Giả sử từ $T_i$ không đi tới được $D_i$. Khi đó tồn tại thứ tự topo đặt thành phần của $D_i$ trước thành phần của $T_i$ (chỉ bị cấm khi thành phần của $T_i$ đi tới được thành phần của $D_i$). Cách gán theo thứ tự đó cho $T_i$ đúng – một cách xếp hợp lệ đặt chi đội $i$ ở bờ Tây, nên $i$ không bị ép ở bờ Đông. $\blacksquare$
Như vậy bài toán quy về: với mỗi $i$, kiểm tra $T_i \leadsto D_i$ và $D_i \leadsto T_i$. Nếu cả hai đều đúng thì không có cách xếp hợp lệ nào (đó chính là điều kiện "cùng thành phần liên thông mạnh").
Cách 1Vét cạn mọi cách xếp – O(2^N · M) · 15%
Thử cả $2^N$ cách xếp bằng đệ quy; với mỗi cách hợp lệ, đánh dấu mỗi chi đội "đã từng ở Đông" / "đã từng ở Tây". Cuối cùng chi đội chỉ từng ở một bờ thì bị ép, từng ở cả hai bờ thì tự do; không có cách hợp lệ nào thì in $-1$.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a, b, col, can;
vector<char> x, y;
bool any_ = false;
void thu(int i) { // chon bo cho doi i, i+1, ..., n
if (i > n) {
for (int j = 0; j < m; j++)
if (col[a[j]] != x[j] && col[b[j]] != y[j]) return; // nguyen vong j khong dat
any_ = true;
for (int j = 1; j <= n; j++) can[j] |= (col[j] == 'D' ? 1 : 2);
return;
}
col[i] = 'D'; thu(i + 1);
col[i] = 'T'; thu(i + 1);
}
int main() {
cin >> n >> m;
a.resize(m); b.resize(m); x.resize(m); y.resize(m); col.assign(n + 1, 0); can.assign(n + 1, 0);
for (int j = 0; j < m; j++) cin >> a[j] >> x[j] >> b[j] >> y[j];
thu(1);
if (!any_) { cout << -1 << "\n"; return 0; }
string s;
for (int j = 1; j <= n; j++) s += (can[j] == 1 ? 'D' : can[j] == 2 ? 'T' : '?');
cout << s << "\n";
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
req = []
for j in range(m):
req.append((int(data[2 + 4 * j]), data[3 + 4 * j], int(data[4 + 4 * j]), data[5 + 4 * j]))
col = [''] * (n + 1)
can = [0] * (n + 1)
found = [False]
def thu(i): # chon bo cho doi i, i+1, ..., n
if i > n:
for a, x, b, y in req:
if col[a] != x and col[b] != y: return # nguyen vong khong dat
found[0] = True
for j in range(1, n + 1):
can[j] |= 1 if col[j] == 'D' else 2
return
col[i] = 'D'; thu(i + 1)
col[i] = 'T'; thu(i + 1)
thu(1)
if not found[0]:
print(-1); return
print(''.join('D' if can[j] == 1 else ('T' if can[j] == 2 else '?') for j in range(1, n + 1)))
main()Cách 2Dựng đồ thị kéo theo, DFS từ từng mệnh đề – O(N · (N + M)) · 35%
Áp dụng thẳng định lý: đánh số mệnh đề $D_i$ là $2i$, $T_i$ là $2i + 1$ (chi đội đánh số từ $0$), thì phủ định của mệnh đề $p$ là p ^ 1. Nguyện vọng "$p$ hoặc $q$" cho hai cung p^1 → q và q^1 → p. Với mỗi chi đội, chạy hai lần DFS: từ $D_i$ có tới $T_i$ không, từ $T_i$ có tới $D_i$ không. Mỗi lần DFS tốn $O(N + M)$, tổng $O(N(N + M))$ – đủ nhanh cho $N \le 2000$.
Các em thử nhập nguyện vọng để xem DFS từ từng mệnh đề đi được tới đâu nhé (các nguyện vọng cách nhau bởi dấu chấm phẩy):
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g; // 2i: "doi i o bo Dong", 2i+1: "doi i o bo Tay"
vector<int> seen; int stamp = 0;
bool reach(int s, int t) { // tu menh de s co suy ra duoc menh de t?
stamp++;
vector<int> st = {s}; seen[s] = stamp;
while (!st.empty()) {
int u = st.back(); st.pop_back();
if (u == t) return true;
for (int v : g[u]) if (seen[v] != stamp) { seen[v] = stamp; st.push_back(v); }
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
g.assign(2 * n, {}); seen.assign(2 * n, 0);
for (int i = 0; i < m; i++) {
int a, b; char x, y;
cin >> a >> x >> b >> y;
int p = 2 * (a - 1) + (x == 'T'), q = 2 * (b - 1) + (y == 'T');
g[p ^ 1].push_back(q); // khong p thi q
g[q ^ 1].push_back(p); // khong q thi p
}
string ans(n, '?');
for (int i = 0; i < n; i++) {
bool dt = reach(2 * i, 2 * i + 1); // neu o bo Dong thi buoc phai o bo Tay
bool td = reach(2 * i + 1, 2 * i); // neu o bo Tay thi buoc phai o bo Dong
if (dt && td) { cout << -1 << "\n"; return 0; }
if (dt) ans[i] = 'T';
if (td) ans[i] = 'D';
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
g = [[] for _ in range(2 * n)] # 2i: "doi i o bo Dong", 2i+1: "doi i o bo Tay"
for j in range(m):
a = int(data[2 + 4 * j]); x = data[3 + 4 * j]; b = int(data[4 + 4 * j]); y = data[5 + 4 * j]
p = 2 * (a - 1) + (1 if x == b'T' else 0)
q = 2 * (b - 1) + (1 if y == b'T' else 0)
g[p ^ 1].append(q) # khong p thi q
g[q ^ 1].append(p) # khong q thi p
seen = [0] * (2 * n)
stamp = 0
ans = ['?'] * n
for i in range(n):
res = []
for s, t in ((2 * i, 2 * i + 1), (2 * i + 1, 2 * i)):
stamp += 1 # tu menh de s co suy ra duoc t?
st = [s]; seen[s] = stamp; ok = False
while st:
u = st.pop()
if u == t: ok = True; break
for v in g[u]:
if seen[v] != stamp:
seen[v] = stamp; st.append(v)
res.append(ok)
dt, td = res
if dt and td:
print(-1); return
if dt: ans[i] = 'T'
if td: ans[i] = 'D'
print(''.join(ans))
main()1 D 2 D; 1 D 2 T), không nguyện vọng nào nói riêng về chi đội 1 nhưng chi đội 1 vẫn bị ép ở bờ Đông.Cách 3Khi mọi nguyện vọng chỉ nối hai chi đội liền nhau – QHĐ trái/phải O(N + M) · 60%
Nếu $|a_j - b_j| \le 1$ thì các chi đội xếp thành một "dãy", mỗi nguyện vọng chỉ ràng buộc một chi đội hoặc hai chi đội kề nhau. Khi đó ta không cần đồ thị:
- $ok[i][v]$: chi đội $i$ được ở bờ $v$ hay không (bị cấm bởi nguyện vọng "$i$ ở $\bar v$ hoặc $i$ ở $\bar v$").
- $bad[i][u][v]$: cặp (chi đội $i$ ở bờ $u$, chi đội $i + 1$ ở bờ $v$) bị cấm bởi nguyện vọng nào đó.
- $f[i][v]$: có cách xếp hợp lệ cho các chi đội $1..i$ (chỉ xét nguyện vọng trong đoạn này) với chi đội $i$ ở bờ $v$: $f[i][v] = ok[i][v] \wedge \bigvee_u (f[i-1][u] \wedge \neg bad[i-1][u][v])$.
- $h[i][v]$: tương tự cho đoạn $i..N$, tính từ phải sang.
Chi đội $i$ ở được bờ $v$ trong một cách xếp hợp lệ $\iff f[i][v] \wedge h[i][v]$ (ghép nửa trái và nửa phải tại $i$). Từ đó suy ra D/T/?. Code dưới giữ lại Cách 2 cho các test không thuộc dạng này.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g;
vector<int> seen; int stamp = 0;
bool reach(int s, int t) { // nhu Cach 2
stamp++;
vector<int> st = {s}; seen[s] = stamp;
while (!st.empty()) {
int u = st.back(); st.pop_back();
if (u == t) return true;
for (int v : g[u]) if (seen[v] != stamp) { seen[v] = stamp; st.push_back(v); }
}
return false;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
vector<int> A(m), B(m); vector<char> X(m), Y(m);
bool adj = true;
for (int i = 0; i < m; i++) {
cin >> A[i] >> X[i] >> B[i] >> Y[i];
if (abs(A[i] - B[i]) > 1) adj = false;
}
if (adj) { // Cach 3: nguyen vong chi noi hai doi lien nhau
// ok[i][v]: doi i duoc o bo v (0 = Dong, 1 = Tay); bad[i][u][v]: cam (doi i = u, doi i+1 = v)
vector<array<int,2>> ok(n + 2, {1, 1});
vector<array<array<int,2>,2>> bad(n + 2);
for (auto &e : bad) e = {{{0, 0}, {0, 0}}};
for (int i = 0; i < m; i++) {
int a = A[i], b = B[i], x = (X[i] == 'T'), y = (Y[i] == 'T');
if (a == b) { if (x == y) ok[a][1 - x] = 0; } // "a o x hoac a o x"
else {
if (a > b) { swap(a, b); swap(x, y); }
bad[a][1 - x][1 - y] = 1; // ca hai deu sai thi khong dat
}
}
vector<array<int,2>> f(n + 2), h(n + 2);
for (int i = 1; i <= n; i++) // f: xet tu trai sang
for (int v = 0; v < 2; v++) {
f[i][v] = ok[i][v] && (i == 1 || (f[i-1][0] && !bad[i-1][0][v]) || (f[i-1][1] && !bad[i-1][1][v]));
}
for (int i = n; i >= 1; i--) // h: xet tu phai sang
for (int v = 0; v < 2; v++) {
h[i][v] = ok[i][v] && (i == n || (h[i+1][0] && !bad[i][v][0]) || (h[i+1][1] && !bad[i][v][1]));
}
if (!f[n][0] && !f[n][1]) { cout << -1 << "\n"; return 0; }
string ans(n, '?');
for (int i = 1; i <= n; i++) {
bool d = f[i][0] && h[i][0], t = f[i][1] && h[i][1];
if (d && !t) ans[i - 1] = 'D';
if (t && !d) ans[i - 1] = 'T';
}
cout << ans << "\n";
return 0;
}
g.assign(2 * n, {}); seen.assign(2 * n, 0); // con lai: Cach 2
for (int i = 0; i < m; i++) {
int p = 2 * (A[i] - 1) + (X[i] == 'T'), q = 2 * (B[i] - 1) + (Y[i] == 'T');
g[p ^ 1].push_back(q);
g[q ^ 1].push_back(p);
}
string ans(n, '?');
for (int i = 0; i < n; i++) {
bool dt = reach(2 * i, 2 * i + 1), td = reach(2 * i + 1, 2 * i);
if (dt && td) { cout << -1 << "\n"; return 0; }
if (dt) ans[i] = 'T';
if (td) ans[i] = 'D';
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
A = [0] * m; B = [0] * m; X = [0] * m; Y = [0] * m
adj = True
for j in range(m):
A[j] = int(data[2 + 4 * j]); X[j] = 1 if data[3 + 4 * j] == b'T' else 0
B[j] = int(data[4 + 4 * j]); Y[j] = 1 if data[5 + 4 * j] == b'T' else 0
if abs(A[j] - B[j]) > 1: adj = False
if adj: # Cach 3: nguyen vong chi noi hai doi lien nhau
ok = [[1, 1] for _ in range(n + 2)] # ok[i][v]: doi i duoc o bo v (0 = Dong, 1 = Tay)
bad = [[[0, 0], [0, 0]] for _ in range(n + 2)] # bad[i][u][v]: cam (doi i = u, doi i+1 = v)
for j in range(m):
a, b, x, y = A[j], B[j], X[j], Y[j]
if a == b:
if x == y: ok[a][1 - x] = 0
else:
if a > b: a, b, x, y = b, a, y, x
bad[a][1 - x][1 - y] = 1
f = [[0, 0] for _ in range(n + 2)]
h = [[0, 0] for _ in range(n + 2)]
for i in range(1, n + 1): # f: xet tu trai sang
for v in range(2):
f[i][v] = ok[i][v] and (i == 1 or (f[i-1][0] and not bad[i-1][0][v]) or (f[i-1][1] and not bad[i-1][1][v]))
for i in range(n, 0, -1): # h: xet tu phai sang
for v in range(2):
h[i][v] = ok[i][v] and (i == n or (h[i+1][0] and not bad[i][v][0]) or (h[i+1][1] and not bad[i][v][1]))
if not f[n][0] and not f[n][1]:
print(-1); return
ans = []
for i in range(1, n + 1):
d = f[i][0] and h[i][0]; t = f[i][1] and h[i][1]
ans.append('D' if d and not t else ('T' if t and not d else '?'))
print(''.join(ans)); return
g = [[] for _ in range(2 * n)] # con lai: Cach 2
for j in range(m):
p = 2 * (A[j] - 1) + X[j]; q = 2 * (B[j] - 1) + Y[j]
g[p ^ 1].append(q); g[q ^ 1].append(p)
seen = [0] * (2 * n); stamp = 0
ans = ['?'] * n
for i in range(n):
res = []
for s, t in ((2 * i, 2 * i + 1), (2 * i + 1, 2 * i)):
stamp += 1
st = [s]; seen[s] = stamp; okr = False
while st:
u = st.pop()
if u == t: okr = True; break
for v in g[u]:
if seen[v] != stamp:
seen[v] = stamp; st.append(v)
res.append(okr)
if res[0] and res[1]:
print(-1); return
if res[0]: ans[i] = 'T'
if res[1]: ans[i] = 'D'
print(''.join(ans))
main()Cách 4Nén thành phần liên thông mạnh + bitset lan truyền trên DAG · 100%
Cách 2 chậm vì mỗi lần DFS lại duyệt lại gần như cả đồ thị. Ta tăng tốc theo ba bước:
- Nén SCC bằng Tarjan (viết khử đệ quy cho an toàn). Các mệnh đề cùng thành phần liên thông mạnh đi tới được nhau, nên chỉ cần xét đồ thị các thành phần – một DAG. Tarjan đánh số thành phần theo thứ tự topo ngược: mọi cung của DAG đi từ số lớn sang số nhỏ. Nếu $D_i$ và $T_i$ cùng thành phần thì in $-1$.
- Chỉ cần kiểm tra một chiều. Trong hai mệnh đề $D_i, T_i$, gọi $t$ là mệnh đề có số thành phần nhỏ hơn (đây cũng là giá trị của $i$ trong nghiệm 2-SAT chuẩn). Không thể có $t \leadsto \neg t$ vì cung chỉ đi từ số lớn sang số nhỏ. Nên chi đội $i$ bị ép (về phía $t$) $\iff$ thành phần của $\neg t$ đi tới được thành phần của $t$.
- Bitset. Ta cần trả lời $N$ câu hỏi "nguồn $src_i$ có tới được đích $dst_i$ không". Xét $64$ chi đội một lượt, mỗi chi đội một bit: đặt bit $i$ ở thành phần $src_i$, rồi đi các thành phần theo thứ tự topo (số giảm dần) và đẩy
reach[d] |= reach[c]theo mỗi cung $c \to d$. Xong lượt, bit $i$ có mặt ở $dst_i$ $\iff$ $src_i \leadsto dst_i$. Mỗi lượt tốn $O(N + M)$ phép OR trên số 64 bit, tổng cộng $O\left(\frac{N}{64}(N + M)\right) \approx 2 \cdot 10^8$ phép tính đơn giản.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> g; // do thi keo theo tren 2n "menh de"
vector<int> comp, low, num, st;
int C = 0, timer_ = 0;
void tarjan(int s) { // Tarjan khu de quy
vector<pair<int,int>> cs = {{s, 0}};
num[s] = low[s] = ++timer_; st.push_back(s);
while (!cs.empty()) {
auto &[u, i] = cs.back();
if (i < (int)g[u].size()) {
int v = g[u][i++];
if (!num[v]) { num[v] = low[v] = ++timer_; st.push_back(v); cs.push_back({v, 0}); }
else if (comp[v] < 0) low[u] = min(low[u], num[v]);
} else {
int x = u; cs.pop_back();
if (!cs.empty()) low[cs.back().first] = min(low[cs.back().first], low[x]);
if (low[x] == num[x]) { // x la goc mot thanh phan lien thong manh
int y;
do { y = st.back(); st.pop_back(); comp[y] = C; } while (y != x);
C++;
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
g.assign(2 * n, {}); // 2i: "doi i o bo Dong", 2i+1: "doi i o bo Tay"
for (int i = 0; i < m; i++) {
int a, b; char x, y;
cin >> a >> x >> b >> y;
int p = 2 * (a - 1) + (x == 'T'), q = 2 * (b - 1) + (y == 'T');
g[p ^ 1].push_back(q); // (p hoac q): khong p thi q
g[q ^ 1].push_back(p); // khong q thi p
}
comp.assign(2 * n, -1); low.assign(2 * n, 0); num.assign(2 * n, 0);
for (int v = 0; v < 2 * n; v++) if (!num[v]) tarjan(v);
for (int i = 0; i < n; i++)
if (comp[2 * i] == comp[2 * i + 1]) { cout << -1 << "\n"; return 0; }
// so hieu thanh phan: Tarjan danh so theo thu tu topo nguoc (canh di tu so lon sang so nho)
vector<vector<int>> dag(C);
for (int u = 0; u < 2 * n; u++)
for (int v : g[u]) if (comp[u] != comp[v]) dag[comp[u]].push_back(comp[v]);
vector<int> src(n), dst(n); // menh de dung trong mot nghiem: comp nho hon
for (int i = 0; i < n; i++) {
int t = (comp[2 * i] < comp[2 * i + 1]) ? 2 * i : 2 * i + 1;
src[i] = comp[t ^ 1]; dst[i] = comp[t]; // doi i bi ep <=> (khong t) keo theo t
}
string ans(n, '?');
vector<unsigned long long> reach(C);
for (int L = 0; L < n; L += 64) { // moi lan xet 64 doi, moi doi mot bit
fill(reach.begin(), reach.end(), 0ULL);
int R = min(n, L + 64);
for (int i = L; i < R; i++) reach[src[i]] |= 1ULL << (i - L);
for (int c = C - 1; c >= 0; c--) // lan theo thu tu topo
if (reach[c]) for (int d : dag[c]) reach[d] |= reach[c];
for (int i = L; i < R; i++)
if (reach[dst[i]] >> (i - L) & 1)
ans[i] = (comp[2 * i] < comp[2 * i + 1]) ? 'D' : 'T';
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
V = 2 * n # 2i: "doi i o bo Dong", 2i+1: "doi i o bo Tay"
eu = [0] * (2 * m); ev = [0] * (2 * m)
deg = [0] * (V + 1)
p = 2
for i in range(m):
a = int(data[p]); x = data[p + 1]; b = int(data[p + 2]); y = data[p + 3]; p += 4
P = 2 * (a - 1) + (1 if x == b'T' else 0)
Q = 2 * (b - 1) + (1 if y == b'T' else 0)
eu[2 * i] = P ^ 1; ev[2 * i] = Q # (P hoac Q): khong P thi Q
eu[2 * i + 1] = Q ^ 1; ev[2 * i + 1] = P # khong Q thi P
deg[P ^ 1] += 1; deg[Q ^ 1] += 1
start = [0] * (V + 1)
for v in range(V): start[v + 1] = start[v] + deg[v]
to = [0] * (2 * m); fill = start[:V]
for e in range(2 * m):
u = eu[e]; to[fill[u]] = ev[e]; fill[u] += 1
# Tarjan khu de quy
comp = [-1] * V; num = [0] * V; low = [0] * V; it = [0] * V
st = []; cs = []; timer = 0; C = 0
for s in range(V):
if num[s]: continue
timer += 1; num[s] = low[s] = timer; st.append(s); cs.append(s); it[s] = start[s]
while cs:
u = cs[-1]
if it[u] < start[u + 1]:
v = to[it[u]]; it[u] += 1
if not num[v]:
timer += 1; num[v] = low[v] = timer; st.append(v); cs.append(v); it[v] = start[v]
elif comp[v] < 0 and num[v] < low[u]:
low[u] = num[v]
else:
cs.pop()
if cs:
w = cs[-1]
if low[u] < low[w]: low[w] = low[u]
if low[u] == num[u]:
while True:
y = st.pop(); comp[y] = C
if y == u: break
C += 1
for i in range(n):
if comp[2 * i] == comp[2 * i + 1]:
sys.stdout.write("-1\n"); return
dag = [[] for _ in range(C)] # canh di tu so hieu lon sang so hieu nho
for u in range(V):
cu = comp[u]
for e in range(start[u], start[u + 1]):
cv = comp[to[e]]
if cv != cu: dag[cu].append(cv)
src = [0] * n; dst = [0] * n; val = [0] * n
tg = [[] for _ in range(C)] # cac doi co "dich" la thanh phan c
for i in range(n):
if comp[2 * i] < comp[2 * i + 1]: t = 2 * i; val[i] = 68 # 'D'
else: t = 2 * i + 1; val[i] = 84 # 'T'
src[i] = comp[t ^ 1]; dst[i] = comp[t]
tg[dst[i]].append(i)
ans = bytearray(b'?' * n)
B = 4096 # moi lan xet B doi, so nguyen lon lam bitset
reach = [0] * C
for L in range(0, n, B):
R = min(n, L + B)
for i in range(L, R): reach[src[i]] |= 1 << (i - L)
for c in range(C - 1, -1, -1): # lan theo thu tu topo
rc = reach[c]
if rc:
for d in dag[c]: reach[d] |= rc
for i in tg[c]:
if L <= i < R and (rc >> (i - L)) & 1: ans[i] = val[i]
reach[c] = 0
sys.stdout.write(ans.decode() + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 (15%) | Sub 2 (20%) | Sub 3 (25%) | Sub 4 (40%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Vét cạn 2^N cách xếp | Đúng | TLE | TLE | TLE | 15 |
| Cách 2 – DFS từ từng mệnh đề O(N(N + M)) | Đúng | Đúng | TLE | TLE | 35 |
| Cách 3 – QHĐ trái/phải khi |a − b| ≤ 1 (còn lại như Cách 2) | Đúng | Đúng | Đúng | TLE | 60 |
| Cách 4 – SCC + bitset trên DAG (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: chỉ lan truyền từ các nguyện vọng "a X a X" | 5/9 | 4/8 | 0/8 | 4/10 | 34,3 |
| Sai: xấp xỉ tập đi tới được bằng khoảng số hiệu thành phần | 4/9 | 1/8 | 1/8 | 1/10 | 16,3 |
Sai: quên xóa mảng reach giữa các lượt 64 chi đội | 9/9 | 1/8 | 3/8 | 1/10 | 30,9 |
| Sai: in ra một nghiệm 2-SAT (nhầm "bị ép" với "một cách xếp") | 3/9 | 1/8 | 0/8 | 0/10 | 7,5 |
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ó 35 test (9 + 8 + 8 + 10), mỗi cách đạt đúng số điểm công bố, còn bốn 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 khoảng 0,45 giây; bản Python sol.py cho cùng đáp án trên mọi test (trên CPython chưa tới 2 giây, các em nhớ chọn PyPy 3 khi nộp). Cách 2 và Cách 3 ở các subtask lớn chạy quá 4 giây mỗi test vì mỗi lần DFS gần như phải đi hết đồ thị (các test có những chuỗi kéo theo dài cả chục nghìn mệnh đề). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian. Lỗi "quên xóa mảng reach" rất khó thấy vì với N ≤ 64 chỉ có một lượt nên nó vẫn đúng ở 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