TLEOJ Contest #14 - Pride Paths

View as PDF

Submit solution

Points: 1800
Time limit: 1.0s
Memory limit: 1G
Input: PPS.inp
Output: PPS.out

Author:
Problem type

Có ai ở đây biết tháng 6 này là tháng dành cho người thuộc nhóm \text{LGBT+} không? Giờ thì bạn biết rồi đấy.
Là một con người theo dõi xã hội phương Tây trong nhiều năm, đó cũng là một phần vinh dự của tôi khi được làm một trong những khán giả xem những người thuộc nhóm \text{LGBT+} diễn hề trong những ngày này. Và có cách gì tốt hơn khi làm điều đó khi gắn nó vào một thứ không liên quan gì tới tháng này nhỉ?

Cho một đồ thị gồm n đỉnh và m cạnh vô hướng, cạnh thứ i nối hai đỉnh u_iv_i.

Đỉnh thứ i chỉ mang đúng một màu, được chọn từ 26 mã màu có sẵn có thể tô lên đồ thị, được đánh dấu từ A đến Z.

Nhận thấy lá cờ mà nhóm \text{LGBT+} vẽ ra cho từng nhóm người có ba dải màu trên từng lá cờ không? Cho một bộ ba mã màu khác nhau z_1 \ne z_2 \ne z_3, tạo thành một xâu Z, cũng như cách lá cờ đó được tô màu vậy. Xác định xem có tồn tại một tập hợp các điểm a_1, a_2 ,a_3 ,..., a_{k - 1}, a_k với chỉ số khác nhau đôi một thỏa mãn rằng:

  • Trong đồ thị con chỉ chứa các đỉnh a_1, a_2, ..., a_{k - 1}, a_k và các cạnh nối giữa hai đỉnh bất kì nằm trong tập này, tồn tại ít nhất một cách di chuyển trên đồ thị đó giữa hai cặp đỉnh bất kì.
  • Màu được tô ở đỉnh a_i chỉ có thể là z_1 hoặc z_2 hoặc z_3, với mọi 1 \le i \le k.
  • Mỗi màu trong số ba màu z_1, z_2, z_3 phải được tô lên ít nhất một trong số k điểm trong tập.

\text{Input} PPS.inp

  • Dòng một gồm ba số n, m (1 \le n \le 10^5; n - 1 \le m \le \text{min}⁡(5*10^5,\frac{n(n-1)}{2}), thể hiện số lượng đỉnh và số lượng cạnh của đồ thị, và q (1 \le q \le 15600), thể hiện số lượng truy vấn.
  • Dòng thứ hai gồm một xâu S được đánh số từ 1 đến n, chỉ gồm các kí tự \text{Latin} hoa, với S[i] thể hiện mã màu của đỉnh thứ i (với 1 \le i \le n).
  • m dòng tiếp theo, dòng thứ i gồm hai số u_i, v_i (1 \le u_i \ne v_i \le n), thể hiện rằng tồn tại một cạnh hai chiều nối giữa hai đỉnh u_iv_i trong đồ thị.
  • q dòng cuối cùng, mỗi dòng gồm một xâu kí tự Z có đúng ba kí tự \text{Latin} hoa, thể hiện một truy vấn. Xâu Z đảm bảo rằng z_1 \ne z_2 \ne z_3.
  • Dữ liệu trong \text{Input} được đảm bảo rằng giữa hai điểm có không quá một cạnh nối giữa chúng và tồn tại ít nhất một cách di chuyển giữa một điểm bất kì tới điểm còn lại.

\text{Output} PPS.out

  • Với mỗi truy vấn, in ra \text{YES} / \text{NO} đối với câu hỏi trên đề với xâu kí tự Z của mỗi truy vấn.

\text{Scoring}

  • Subtask \text{#}1 (50\% số điểm): n \le 26; các S[i] khác nhau đôi một.
  • Subtask \text{#}2 (30\% số điểm): m = n - 1.
  • Subtask \text{#}3 (20\% số điểm): Không có điều kiện gì thêm.

\text{Examples}

\text{Test #}1

\text{Input}

6 7 3
ABDEBC
1 2
5 3
1 3
2 3
5 2
4 2
5 6
ABC
AEC
AZC

\text{Output}

YES
NO
NO
\text{Explanations}

Ở testcase \text{#}2\text{#}3, không tồn tại một bộ a_i phù hợp.
Ở testcase \text{#}1, bộ a_i phù hợp và duy nhất phù hợp là [1; 2; 5; 6].

Bộ đỉnh này thỏa mãn vì tồn tại một cách di chuyển giữa các cặp đỉnh (1; 2), (1; 5), (1; 6), (2; 5), (2; 6), (5; 6), và màu được tô ở bốn đỉnh này là \text{A}, \text{B} (ở đỉnh 25), và \text{C}.


Comments

There are no comments at the moment.