TLEOJ Contest #14 - Everyone Everywhere Cheating All At Once

Điểm: 1600

Thời gian: 1.0s

Bộ nhớ: 1G

Input: EECAAO.inp

Output: EECAAO.out

Tác giả:

Noobcoder

Dạng bài

Reset não xong chưa? Đọc đề tiếp nè.

Nếu không có hứng thú đọc đề, vui lòng đọc từ đoạn thứ 3 của đề bài.

Nói sơ một chút về các trò chơi. Một trò chơi không thể hay nếu không có một chuỗi những sự kiện liên tiếp giữa các người chơi, liên tục đưa ra các nước đi mà họ cho là hợp lí nhất để tạo cho họ một lợi thế dẫn trước những người chơi khác, từ đó dẫn đến chiến thắng. Những trường hợp đó, chúng ta có thể gọi là một $\text{Event Sequence Simulation}$ , khi mà các hành động của người chơi này có thể ảnh hưởng một phần hoặc toàn bộ, trực tiếp hoặc gián tiếp lên lối chơi của những người khác.

Hai học sinh quyết định thử nghiệm về tình huống này. Tạm gọi hai người này với nickname $\text{Alan}$ và $\text{Bob}$ , vì tôi không muốn expose tên hai người đã thực sự làm điều này. Họ quyết định lấy bộ bài $\text{Yugioh}$ mà họ đã sưu tập từ lâu ra để thử. Sở dĩ họ chọn trò đấu bài này vì tình huống $\text{chain}$ hiệu ứng của lá bài của mình lên lá bài của đối thủ rất thường xuyên xảy ra, với các lá $\text{Quick Spells}$ và $\text{Counter Traps}$ , và đôi khi là từ hiệu ứng quái thú.

Tại một thời điểm trong ván đấu, sau khi một người chơi nào đó đã thực hiện một tác vụ nào đó, hai người chơi đang ở một cây trò chơi, với gốc của cây là tình huống hai người đang ở hiện tại. Cây trò chơi bao gồm $n$ game-states, được đánh số từ $1$ đến $n$ , và hai người đang ở game-state $\text{#}1$ , là gốc của cây. Có $n - 1$ cách để tiếp tục cho tình huống tiếp diễn, phương án thứ $i$ được biểu diễn bởi một cạnh có hướng từ game-state $\text{#}u_i$ đến game-state $\text{#}v_i$ , biểu thị tại game-state $\text{#}u_i$ , phương án thứ $i$ đó sẽ đưa cả hai người đến với game-state $\text{#}v_i$ . Trên cạnh đó được gán một chữ cái, được lấy từ chữ cái đầu từ nickname của họ ( $\text{A}$ hoặc $\text{B}$ ), cho biết rằng trò chơi chỉ được tiếp tục bằng cách đi qua cạnh đó bởi $\text{Alan}$ (nếu đó là kí tự $\text{A}$ ), hoặc $\text{Bob}$ (nếu đó là kí tự $\text{B}$ ). Game-state $\text{#}i$ (trong máy tính phân tích) sẽ có một chỉ số $P[i]$ , biểu thị rằng:

Nếu $P[i] = 1$ , nghĩa là $\text{Alan}$ sẽ có lợi thế, nếu tình huống dừng tại game-state $\text{#}i$ .
Nếu $P[i] = -1$ , nghĩa là $\text{Bob}$ sẽ có lợi thế, nếu tình huống dừng tại game-state $\text{#}i$ .
Nếu $P[i] = 0$ , nghĩa là trò chơi vẫn sẽ ở thế cân bằng, nếu tình huống dừng tại game-state $\text{#}i$ .

Dù là một trò chơi tình nghĩa anh em và mang tính chất nghiên cứu, nhưng cả hai không biết rằng, đối thủ của mình đã kịp và lén lút gian lận, sử dụng máy tính để phân tích ra cây trò chơi mà đã được phân tích ở trên. Họ quyết định từ đầu, rằng ở một game-state, mỗi người sẽ có hai lựa chọn là $\text{stop}$ và $\text{continue}$ . Người nào không thực hiện action gần nhất trước khi đến game-state này sẽ được quyết định trước. Tình huống sẽ được xử lí như sau:

Nếu cả hai người chọn $\text{stop}$ , tình huống sẽ dừng tại game-state đó.
Nếu có đúng một người chọn $\text{continue}$ , người chọn $\text{continue}$ sẽ được chọn một hướng đi có ghi chữ cái đầu tên họ và tiếp tục diễn biến của tình huống đó.
Nếu cả hai người chọn $\text{continue}$ , để tránh xô xát không cần thiết, hai người quyết định rằng người được ưu tiên chọn ở lượt này sẽ được thực hiện hành động tiếp theo.

Lưu ý: Chỉ có người có thể thực hiện hành động để tiếp tục tình huống mới được chọn $\text{continue}$ . Nếu họ không thể tự mình tiếp tục, lựa chọn của họ sẽ mặc định là $\text{stop}$ .

Vì cả hai người đều gian lận, nên họ sẽ dựa trên thông tin đó để tạo được lợi thế lớn nhất cho bản thân họ.

Hãy cho biết trong một khoảnh khắc nào đó, hai người đang ở game-state $\text{#}i$ , thì lợi thế sẽ thuộc về ai? Biết rằng câu hỏi này yêu cầu bạn sẽ trả lời dựa trên các parallel universes, mà ở mỗi universes như thế, hai người chơi thay vì xuất phát từ game-state $\text{#}1$ , thì ở các parallel universes khác, hai người đó phải đến game-state $\text{#}i$ mới bắt đầu gian lận. Ngoài điều đó ra, cây trò chơi phân tích được, và các luật lệ ở các parallel universes đang xét đến này đều giống nhau.

$\text{Input}$ EECAAO.inp

Dòng một gồm một số $n$ $(1 \le n \le 2 * 10^5)$ , thể hiện số lượng game-states.
Dòng thứ hai, có $n$ số biểu thị mảng $P$ , với số thứ $i$ biểu thị giá trị của $P[i]$ $(-1 \le P[i] \le 1)$ .
$n$ dòng tiếp theo, dữ liệu được biểu diễn như sau:
- Dòng đầu tiên, sẽ có hai số $0$ , $1$ , và một chữ cái $l_1$ $(l_1 \in \{A; B\})$ . Điều này để tránh softlock ngay ở game-state $\text{#}1$ , khi trong cây trò chơi được miêu tả trên đề không cho biết rằng ai là người đã thực hiện hành động gần nhất trước khi ở game-state gốc.
- $n - 1$ dòng còn lại, cây trò chơi sẽ được biểu diễn như bình thường. Có tổng cộng $n - 1$ bộ dữ liệu, bộ dữ liệu thứ $i$ $(2 \le i \le n)$ có dạng hai số $u_i$ và $v_i$ , và một kí tự $l_i$ ( $1 \le u_i \ne v_i \le n$ ; $l_i \in \{A; B\}$ ), thể hiện rằng có một cạnh có hướng nối giữa game-state $\text{#}u_i$ và game-state $\text{#}v_i$ , và chỉ có người có chữ cái đầu trong nickname trùng với $l_i$ mới đưa trò chơi đi theo cạnh đó. Trong một số tình huống, ta có thể nói $l_{u_i \rightarrow v_i} = l_i$ .
Dữ liệu của cây trò chơi được biểu diễn theo cách sao cho từ game-state $\text{#}1$ , tồn tại một cách điều khiển không-thời gian tới tất cả $n - 1$ game-states còn lại.

$\text{Output}$ EECAAO.out

Gồm $n$ số trên một dòng. Số thứ $i$ biểu diễn cán cân lợi thế giữa hai người chơi Alan và Bob trong tình huống, tại một parallel universe mà hai người sẽ bắt đầu gian lận tại game-state $\text{#}i$ , giống như cách mà $P[i]$ được định nghĩa (trên đề).

$\text{Scoring}$

Subtask $\text{#}1$ ( $10\%$ số điểm): $u_i = 1$ .
Subtask $\text{#}2$ ( $20\%$ số điểm): $l_i = \text{A}$ hoặc $l_i = \text{B}$ .
Subtask $\text{#}3$ ( $30\%$ số điểm): Đồ thị được cho có dạng một đường thẳng.
Subtask $\text{#}4$ ( $10\%$ số điểm): Game-state gốc sẽ nối đến hai game-state khác, trong khi các game-state $\text{#}u$ $(u > 1)$ chỉ nối đến với nhiều nhất một game-state khác.
Subtask $\text{#}5$ ( $10\%$ số điểm): Gọi $c(u) = [v_1; v_2; ...; v_k]$ là tập hợp chỉ số của các game-state mà game-state $\text{#}u$ có một cạnh chỉ tới. Dữ liệu thỏa mãn (nếu game-state $\text{#}u$ có cạnh được nối tới các game-state khác) $l_{u \rightarrow v_1} = l_{u \rightarrow v_2} = ... = l_{u \rightarrow v_k}$ .
Subtask $\text{#}6$ ( $20\%$ số điểm): Không có giới hạn gì thêm.

$\text{Examples}$

Ở trong các test này, ta sẽ giả định giá trị $E[i]$ là đáp án thứ $i$ cần được in ra $\text{Output}$ .

$\text{Test #}1$

$\text{Input}$

$\text{Output}$

-1 -1 -1

$\text{Explanations}$

Đầu tiên, cần nhận thấy rằng mọi $l_i = B$ $(i > 1)$ , nên ở mọi game-state $\text{#}1$ , $\text{#}2$ , $\text{#}3$ thì $\text{Alan}$ chỉ có thể chọn $\text{stop}$ , do $\text{Alan}$ không thể tự mình tiếp tục cho tình huống diễn biến.
Xét game-state $\text{#}3$ : Nếu tình huống dừng lại tại game-state này, $\text{Bob}$ chắc chắn có được lợi thế do $P[3] = -1$ . Suy ra, $E[3] = -1$ .
Xét game-state $\text{#}2$ : Dù $\text{Bob}$ chọn $\text{stop}$ hay $\text{continue}$ thì kết quả Bob nhận được luôn có lợi cho Bob ( $P[2] = -1$ và $E[3] = -1$ ), $\text{Bob}$ chắc chắn có được lợi thế. Suy ra $E[2] = -1$ .
Xét game-state $\text{#}1$ : Nếu $\text{Bob}$ chọn $\text{stop}$ , vì $\text{Alan}$ buộc phải chọn $\text{stop}$ nên tình huống sẽ kết thúc với kết quả hai người huề, vì $P[1] = 0$ . Trong khi đó, nếu $\text{Bob}$ chọn $\text{continue}$ , cả hai người sẽ đến với game-state $\text{#}2$ và $E[2] = -1$ , $\text{Bob}$ có được lợi thế. Vì $\text{Bob}$ chơi tối ưu nên $\text{Bob}$ sẽ chọn $\text{continue}$ ở game-state này và chắc chắn có được lợi thế. Suy ra $E[1] = -1$ .

Vì ở cả ba game-states, nếu $\text{Bob}$ chơi tối ưu thì sẽ luôn có được lợi thế, nên cả ba số cần in ra là $-1$ .

$\text{Test #}2$

$\text{Input}$

$\text{Output}$

0 1 -1 1

$\text{Explanations}$

Xét đồng thời cả ba game-state $\text{#}2$ , $\text{#}3$ , $\text{#}4$ : Nếu tình huống dừng lại tại các game-state này, $\text{Bob}$ chắc chắn có được lợi thế ở game-state $\text{#}3$ $(P[3] = -1)$ , và $\text{Alan}$ có lợi thế ở game-state $\text{#}2$ và $\text{#}4$ $(P[2] = P[4] = 1)$ . Suy ra $E[3] = -1$ , $E[2] = E[4] = 1$ .
Xét game-state $\text{#}1$ : Ở game-state này, $\text{Bob}$ được ưu tiên chọn trước. Nhận thấy rằng nếu chọn $\text{continue}$ , $\text{Alan}$ chọn gì cũng đem lại lợi thế cho anh ta (vì ở hai game-state $\text{#}2$ và $\text{#}4$ , hai game-state mà $\text{Bob}$ sẽ đưa trò chơi tới, $E[2] = E[4] = 1$ , không quan trọng $\text{Alan}$ chọn gì do $\text{Bob}$ có quyền ưu tiên), nên $\text{Bob}$ quyết định chọn $\text{stop}$ , bởi với quyết định này, $\text{Bob}$ chắc chắn không thiệt, do hai trường hợp có thể xảy ra là: hoặc $\text{Alan}$ chọn $\text{continue}$ và đem lại lợi thế cho $\text{Bob}$ (do ở game-state $\text{#}3$ mà $\text{Alan}$ có thể đưa trò chơi tới, $E[3] = -1$ ) hoặc $\text{Alan}$ chọn $\text{stop}$ và cả hai huề $(P[1] = 0)$ . Về phần $\text{Alan}$ , vì cũng đang chọn phương án tối ưu nên $\text{Alan}$ cũng chọn $\text{stop}$ , và cả hai huề ở trường hợp này. Suy ra $E[1] = 0$ .

$\text{Test #}3$

$\text{Input}$

6
0 -1 1 1 -1 -1
0 1 A
1 2 A
1 3 B
2 4 B
2 5 B
3 6 A

$\text{Output}$

0 -1 1 1 -1 -1

$\text{Explanations}$

Xét game-state $\text{#}4$ , $\text{#}5$ , $\text{#}6$ : $\text{Alan}$ sẽ có lợi thế ở game-state $\text{#}4$ , còn $\text{Bob}$ sẽ có lợi thế ở game-state $\text{#}5$ và $\text{#}6$ . Suy ra, $E[4] = 1$ , $E[5] = E[6] = -1$ .
Xét game-state $\text{#}3$ : Ở đây, $\text{Bob}$ chỉ được phép chọn $\text{stop}$ và $\text{Alan}$ được quyền ưu tiên. $\text{Alan}$ sẽ chọn $\text{stop}$ để đảm bảo lợi thế của anh ta $(P[3] = 1)$ , vì nếu chọn $\text{continue}$ thì tình huống sẽ đến với game-state $\text{#}6$ , cũng coi như là đưa lợi thế cho $\text{Bob}$ (do $E[6] = -1$ ). Suy ra, $P[3] = 1$ .
Xét game-state $\text{#}2$ : $\text{Bob}$ được quyền ưu tiên, và $\text{Alan}$ buộc phải chọn $\text{stop}$ . Trong tình huống này, dù $\text{Bob}$ có chọn gì thì kết quả đều thuận lợi cho $\text{Bob}$ , nếu $\text{Bob}$ chơi tối ưu (do $\text{P[2] = -1}$ và nếu Bob thích chọn $\text{continue}$ , chỉ cần đưa trò chươi đến với game-state $\text{#}5$ và Bob sẽ có lợi thế do $E[5] = -1$ ). Suy ra, $P[2] = -1$ .
Xét game-state $\text{#}1$ : $\text{Bob}$ được quyền ưu tiên. Tuy nhiên, nếu $\text{Bob}$ chọn $\text{continue}$ thì cách duy nhất để $\text{Bob}$ tiếp tục tình huống là đưa tới game-state $\text{#}3$ và $E[3] = 1$ , vì thế nên lựa chọn tốt nhất cho $\text{Bob}$ là $\text{stop}$ , vì $\text{Bob}$ sẽ chắc chắn không thiệt với lựa chọn này (do nếu $\text{Alan}$ chọn $\text{continue}$ , $\text{Bob}$ sẽ thắng tại game-state $\text{#}2$ và $E[2] = -1$ , còn nếu chọn $\text{stop}$ thì sẽ hòa do $P[1] = 0$ ). Tương tự, $\text{Alan}$ biết rằng chọn $\text{continue}$ cũng dẫn đến việc tình huống sẽ tiếp diễn tại game-state $\text{#}2$ mà $E[2]=-1$ , nên $\text{Alan}$ cũng sẽ chọn $\text{stop}$ . Vậy là cả hai người quyết định $\text{stop}$ và huề. Suy ra $P[1] = 0$ .

Bình luận

Không có bình luận nào.