Hướng dẫn giải của [Beginner Free Contest 17] REPEAT
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đồ thị ~x \to a_x~ có mỗi đỉnh một cạnh ra. Quá trình dừng khi gặp điểm cố định (~a_x = x~); nếu đi vào chu trình dài hơn 1 thì vô hạn (in ~-1~). Phép gán cuối cùng (không làm ~x~ đổi) cũng được tính là một phép biến đổi, nên một điểm cố định có đáp án 1 (khớp ví dụ: ~5 \to 6 \to 6~ cho đáp án 2).
Sub 1: Mô phỏng — ~O(n \cdot q)~, dùng khi ~n, q \le 10^3~
Với mỗi truy vấn, mô phỏng tối đa ~n+1~ bước; nếu chưa gặp điểm cố định thì in ~-1~. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: BFS trên đồ thị ngược — ~O(n + q)~
Đặt ~f[i] = 1~ với mọi điểm cố định, rồi BFS theo cạnh ngược: ~f[v] = f[a_v] + 1~. Đỉnh không được thăm có ~f = -1~. Trả lời mỗi truy vấn bằng ~f[x]~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~n, q \le 10^3~ gọi sub1 (8 test), còn lại gọi sub2 (12 test). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, q;
int a[200005], qs[200005];
// Sub 1: mô phỏng từng truy vấn — O(n * q), dùng khi n, q <= 1000
void sub1() {
for (int t = 0; t < q; t++) {
int x = qs[t], steps = 0, ans = -1;
// sau n+1 bước mà chưa dừng thì x đã đi vào chu trình dài hơn 1: vô hạn
for (steps = 1; steps <= n + 1; steps++) {
int y = a[x];
if (y == x) { ans = steps; break; } // bước này không làm x đổi: dừng
x = y;
}
cout << ans << (t + 1 < q ? ' ' : '\n');
}
}
// Sub 2: dựng đồ thị ngược, BFS từ các điểm cố định a[i] = i — O(n + q)
void sub2() {
vector<vector<int>> rev(n + 1);
vector<int> f(n + 1, -1);
queue<int> Q;
for (int i = 1; i <= n; i++) {
if (a[i] == i) { f[i] = 1; Q.push(i); } // đã là điểm cố định: đúng 1 phép gán
else rev[a[i]].push_back(i);
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int v : rev[u]) { f[v] = f[u] + 1; Q.push(v); }
}
for (int t = 0; t < q; t++) cout << f[qs[t]] << (t + 1 < q ? ' ' : '\n');
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> q;
for (int i = 0; i < q; i++) cin >> qs[i];
if (n <= 1000 && q <= 1000) sub1();
else sub2();
return 0;
}
Bình luận