Kiến trúc sư Timothy đã thiết kế một trò chơi thoát hiểm mới. Trong trò chơi có \(n\) phòng, được đánh số từ \(0\) đến \(n-1\). Ban đầu, mỗi phòng có đúng một chìa khóa. Mỗi chìa khóa thuộc một loại, là một số nguyên từ \(0\) đến \(n-1\), bao gồm cả hai đầu mút. Chìa khóa trong phòng \(i\) (\(0 \le i \le n-1\)) thuộc loại \(r[i]\). Lưu ý rằng nhiều phòng có thể chứa chìa khóa cùng loại, tức là các giá trị \(r[i]\) không nhất thiết khác nhau.

Trò chơi còn có \(m\) đường kết nối hai chiều, được đánh số từ \(0\) đến \(m-1\). Đường kết nối \(j\) (\(0 \le j \le m-1\)) nối hai phòng khác nhau \(u[j]\) và \(v[j]\). Một cặp phòng có thể được nối bằng nhiều đường kết nối.

Trò chơi dành cho một người chơi, thu thập chìa khóa và di chuyển giữa các phòng qua các đường kết nối. Người chơi đi qua đường kết nối \(j\) khi sử dụng nó để di chuyển từ phòng \(u[j]\) đến phòng \(v[j]\) hoặc ngược lại. Người chơi chỉ có thể đi qua đường kết nối \(j\) nếu trước đó đã thu thập được một chìa khóa loại \(c[j]\).

Tại bất kỳ thời điểm nào trong trò chơi, người chơi đang ở một phòng \(x\) và có thể thực hiện hai loại hành động:

• Thu thập chìa khóa loại \(r[x]\) trong phòng \(x\) (nếu chưa thu thập chìa khóa đó).
• Đi qua một đường kết nối \(j\) có \(u[j] = x\) hoặc \(v[j] = x\), nếu trước đó đã thu thập được một chìa khóa loại \(c[j]\). Lưu ý rằng người chơi không bao giờ bỏ đi chìa khóa đã thu thập.

Người chơi bắt đầu trò chơi tại một phòng \(s\) mà không mang theo chìa khóa nào. Phòng \(t\) được gọi là có thể đến được từ phòng \(s\) nếu người chơi bắt đầu ở phòng \(s\) có thể thực hiện một dãy hành động như trên để đến phòng \(t\).

Với mỗi phòng \(i\) (\(0 \le i \le n-1\)), gọi \(p[i]\) là số phòng có thể đến được từ phòng \(i\). Timothy muốn biết tập hợp các chỉ số \(i\) đạt giá trị \(p[i]\) nhỏ nhất trong tất cả các chỉ số \(0 \le i \le n-1\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u,
                                std::vector<int> v, std::vector<int> c);

• r: mảng độ dài \(n\). Với mỗi \(i\) (\(0 \le i \le n-1\)), chìa khóa trong phòng \(i\) thuộc loại \(r[i]\).
• u, v: hai mảng độ dài \(m\). Với mỗi \(j\) (\(0 \le j \le m-1\)), đường kết nối \(j\) nối hai phòng \(u[j]\) và \(v[j]\).
• c: mảng độ dài \(m\). Với mỗi \(j\) (\(0 \le j \le m-1\)), loại chìa khóa cần để đi qua đường kết nối \(j\) là \(c[j]\).
• Hàm phải trả về mảng \(a\) độ dài \(n\). Với mỗi \(0 \le i \le n-1\), \(a[i]\) phải bằng \(1\) nếu \(p[i] \le p[j]\) với mọi \(j\) thỏa mãn \(0 \le j \le n-1\). Ngược lại, \(a[i]\) phải bằng \(0\).

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(r[0]\ r[1]\ \ldots\ r[n-1]\).
• Dòng \(3+j\) (\(0 \le j \le m-1\)): \(u[j]\ v[j]\ c[j]\).

Dữ liệu ra

Trình chấm mẫu in giá trị trả về của find_reachable theo định dạng sau:

• Dòng \(1\): \(a[0]\ a[1]\ \ldots\ a[n-1]\).

Ràng buộc

• \(2 \le n \le 300\,000\).
• \(1 \le m \le 300\,000\).
• \(0 \le r[i] \le n-1\) với mọi \(0 \le i \le n-1\).
• \(0 \le u[j], v[j] \le n-1\) và \(u[j] \ne v[j]\) với mọi \(0 \le j \le m-1\).
• \(0 \le c[j] \le n-1\) với mọi \(0 \le j \le m-1\).

Phân nhóm

Ví dụ

find_reachable([0, 1, 1, 2],
               [0, 0, 1, 1, 3], [1, 2, 2, 3, 1], [0, 0, 1, 0, 2])

[0, 1, 1, 0]

find_reachable([0, 1, 1, 2, 2, 1, 2],
               [0, 0, 1, 1, 2, 3, 3, 4, 4, 5],
               [1, 2, 2, 3, 3, 4, 5, 5, 6, 6],
               [0, 0, 1, 0, 0, 1, 2, 0, 2, 1])

[0, 1, 1, 0, 1, 0, 1]

find_reachable([0, 0, 0], [0], [1], [0])

[0, 0, 1]

Nguồn

IOI 2021, Ngày 1 — Keys (keys).