3. IOI 2018 - Werewolf
Quận Ibaraki ở Nhật Bản có \(N\) thành phố và \(M\) con đường. Các thành phố được đánh số từ \(0\) đến \(N-1\) theo thứ tự tăng dần về dân số. Mỗi con đường nối một cặp hai thành phố khác nhau và có thể di chuyển theo cả hai hướng. Bạn có thể sử dụng một hoặc nhiều con đường này để di chuyển từ một thành phố bất kỳ đến một thành phố bất kỳ khác.
Bạn lên kế hoạch gồm \(Q\) chuyến đi, được đánh số từ \(0\) đến \(Q-1\). Chuyến đi \(i\) (\(0 \le i \le Q-1\)) sẽ di chuyển từ thành phố \(S_i\) đến thành phố \(E_i\).
Bạn là người sói. Bạn có hai hình dáng: hình dáng người và hình dáng sói. Tại thời điểm bắt đầu mỗi chuyến đi, bạn ở hình dáng người. Kết thúc chuyến đi, bạn bắt buộc phải ở hình dáng sói. Trong chuyến đi, bạn phải chuyển đổi (chuyển từ hình dáng người sang hình dáng sói) đúng một lần. Bạn chỉ có thể chuyển đổi khi đang ở một thành phố nào đó, kể cả \(S_i\) hoặc \(E_i\).
Cuộc sống của người sói không dễ dàng. Bạn phải tránh ở hình dáng người khi ở các thành phố ít dân và tránh ở hình dáng sói khi ở các thành phố đông dân. Với mỗi chuyến đi \(i\) (\(0 \le i \le Q-1\)), có hai ngưỡng \(L_i\) và \(R_i\) (\(0 \le L_i \le R_i \le N-1\)) chỉ ra các thành phố phải tránh. Cụ thể, bạn không được ở hình dáng người khi ở các thành phố \(0,1,\ldots,L_i-1\), và không được ở hình dáng sói khi ở các thành phố \(R_i+1,R_i+2,\ldots,N-1\). Điều đó có nghĩa là trong chuyến đi \(i\), bạn chỉ được chuyển đổi hình dáng ở một trong các thành phố \(L_i,L_i+1,\ldots,R_i\).
Nhiệm vụ của bạn là xác định, đối với mỗi chuyến đi, có tồn tại cách di chuyển từ thành phố \(S_i\) đến thành phố \(E_i\) thỏa mãn tất cả các điều kiện trên hay không. Đường đi của bạn có thể có độ dài bất kỳ.
Chi tiết cài đặt
Bạn cần cài đặt hàm sau:
int[] check_validity(int N, int[] X, int[] Y, int[] S, int[] E, int[] L, int[] R)
N: số lượng thành phố.X,Y: các mảng có độ dài \(M\). Với mỗi \(j\) (\(0 \le j \le M-1\)), thành phốX[j]được nối trực tiếp với thành phốY[j]bởi một con đường.S,E,L,R: các mảng có độ dài \(Q\), biểu diễn các chuyến đi.
Chú ý rằng \(M\) và \(Q\) là độ dài của các mảng; cách lấy độ dài mảng được mô tả trong phần Lưu ý cài đặt.
Hàm check_validity được gọi đúng một lần cho mỗi bộ dữ liệu. Hàm này phải trả về một mảng số nguyên \(A\) có độ dài \(Q\). Giá trị \(A_i\) (\(0 \le i \le Q-1\)) phải là \(1\) nếu chuyến đi \(i\) có thể thực hiện được và thỏa mãn các điều kiện đã nêu, hoặc \(0\) trong trường hợp ngược lại.
Trong C++, giao diện trong tệp werewolf.h của gói đính kèm là:
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R);
Ví dụ
Cho \(N=6\), \(M=6\), \(Q=3\), \(X=[5,1,1,3,3,5]\), \(Y=[1,2,3,4,0,2]\), \(S=[4,4,5]\), \(E=[2,2,4]\), \(L=[1,2,3]\) và \(R=[2,2,4]\).
Trình chấm gọi check_validity(6, [5, 1, 1, 3, 3, 5], [1, 2, 3, 4, 0, 2], [4, 4, 5], [2, 2, 4], [1, 2, 3], [2, 2, 4]).
Với chuyến đi \(0\), bạn có thể di chuyển từ thành phố \(4\) đến thành phố \(2\) như sau:
- Bắt đầu tại thành phố \(4\) (bạn ở hình dáng người).
- Di chuyển đến thành phố \(3\) (bạn ở hình dáng người).
- Di chuyển đến thành phố \(1\) (bạn ở hình dáng người).
- Chuyển đổi từ hình dáng người sang hình dáng sói (bạn ở hình dáng sói).
- Di chuyển đến thành phố \(2\) (bạn ở hình dáng sói).
Với chuyến đi \(1\) và \(2\), bạn không thể di chuyển giữa các thành phố đã cho mà thỏa mãn các điều kiện.
Do đó, chương trình của bạn phải trả lại \([1,0,0]\).
Các tệp sample-01-in.txt và sample-01-out.txt trong gói nén zip đính kèm tương ứng với ví dụ này. Gói đính kèm còn chứa một cặp tệp dữ liệu vào/ra mẫu khác.
Hạn chế
- \(2 \le N \le 200\,000\).
- \(N-1 \le M \le 400\,000\).
- \(1 \le Q \le 200\,000\).
- Với mỗi \(0 \le j \le M-1\): \(0 \le X_j \le N-1\), \(0 \le Y_j \le N-1\) và \(X_j \ne Y_j\).
- Bạn có thể di chuyển từ một thành phố bất kỳ đến một thành phố bất kỳ khác bằng cách sử dụng các con đường.
- Mỗi cặp thành phố được nối trực tiếp với nhau bởi nhiều nhất một con đường. Nói cách khác, với mọi \(0 \le j < k \le M-1\), \((X_j,Y_j) \ne (X_k,Y_k)\) và \((Y_j,X_j) \ne (X_k,Y_k)\).
- Với mỗi \(0 \le i \le Q-1\): \(0 \le L_i \le S_i \le N-1\), \(0 \le E_i \le R_i \le N-1\), \(S_i \ne E_i\) và \(L_i \le R_i\).
Phân nhóm
| Subtask | Điểm | Hạn chế bổ sung |
|---|---|---|
| \(1\) | \(7\) | \(N \le 100\), \(M \le 200\), \(Q \le 100\). |
| \(2\) | \(8\) | \(N \le 3\,000\), \(M \le 6\,000\), \(Q \le 3\,000\). |
| \(3\) | \(34\) | \(M=N-1\) và mỗi thành phố là đầu mút của nhiều nhất \(2\) con đường (các thành phố được nối thành một đường). |
| \(4\) | \(51\) | Không có hạn chế bổ sung. |
Trình chấm mẫu
Trình chấm mẫu đọc dữ liệu vào theo khuôn dạng sau:
- Dòng \(1\): \(N\ M\ Q\).
- Dòng \(2+j\) (\(0 \le j \le M-1\)): \(X_j\ Y_j\).
- Dòng \(2+M+i\) (\(0 \le i \le Q-1\)): \(S_i\ E_i\ L_i\ R_i\).
Trình chấm mẫu in ra giá trị trả về của check_validity theo khuôn dạng sau:
- Dòng \(1+i\) (\(0 \le i \le Q-1\)): \(A_i\).
Dữ liệu vào của ví dụ trên:
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4Dữ liệu ra tương ứng:
1
0
0