CoTreeGame - Colored Tree Game
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 5.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: chandoi

Nguồn: ACM-ICPC Vietnam Central Provincial Contest 

Chú ý: bộ test do mình make(có thể có lỗi), không phải bộ test chính thức của kì thi


Jack recently discovered a game called Colored Tree. The game is played on a tree containing N nodes in which nodes are numbered from 0 to N - 1 and edges are of four colors: red (R), green (G), blue (B) and white (W). An order of four colors is also given. The player are required to answer multiple questions, each of them is described as below:

    •    Given two distinct nodes X and Y, we now consider the path connecting X and Y in the tree.

    •    In each turn, the player can select two adjacent edges (edges are adjacent iff they have a common node), merge them into a new edge and remove the common node.

    •    Let u and v be the colors of the selected edges, the new edge's color will be determined by these rules:

            •    If either u or v is white, it will be the other color.

            •    If u and v are the same, it will be white.

            •    Otherwise, if u and v are different, it will be the remaining color in (red, green, blue). For example: if u is red and v is blue then the new color will be green.

    •    The player will keep merging edges until only one edge remains. The last edge's color should be as good as possible. Color u is better than color v iff u appears before v in the color order.

Being a smart kid, Jack soon finds that the game is not challenging enough for him. Hence, he invents a new version which is played on a dynamic tree. Specifically, the tree initially contains only one node and there are two types of operations: adding a new edge to the existing tree and answering a question.

Let D be a variable we will use to generate input. D is initally 0. Also, let count(c) be the number of times color c has been the answer so far. All the count values are initially 0, too.

Initially, the tree only has one node, numbered 0.


The first line contains the number of tests T.

Each test contains:

    •    The first line contains the number of queries Q and the color order S.

    •    Line i of the following Q lines contains:

            •    0 K c: This describes a query of adding a new edge. Let N be the current number of nodes. We will add a new edge of color c between N and X where X = (D + K) mod N.

            •    1 X Y: This describes a question for the path connecting X and Y. Let c be the answer for this question, we will first increase count(c) by 1, then set D = count(c) after this query.


Print T lines, each line contains all characters (R, G, B, W) representing the answers for one test.


T ≤ 10

1 ≤ Q ≤ 500000

0 ≤ K ≤ 1000000

0 ≤ X, Y < current number of nodes and X ≠ Y

S contains exactly 4 different characters from {R, G, B, W}

Ví dụ

  • input
    5 RGBW
    0 0 W
    0 1 R
    1 0 2
    0 0 R
    1 2 3
    4 RGBW
    0 0 R
    0 1 B
    0 2 W
    1 0 3
Back to Top