Đi Dự Tiệc COW

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò đánh số từ $1$ đến $N$ , mỗi con có một bạn thân $a_{i}$ . Trong $M$ đêm liên tiếp, các con bò tổ chức tiệc loại "C", "O", hoặc "W".

Mỗi đêm, khi bò $c_{i}$ tổ chức tiệc loại $v_{i}$ , tiệc đó tồn tại cho đến khi một loại khác được tổ chức tại cùng bò đó. Các bò không tổ chức tiệc sẽ kiểm tra chuồng bạn thân. Nếu bạn thân không có tiệc, bò đi theo bạn thân (và bạn thân đó cũng đi theo bạn thân của mình, v.v.). Bò không thể đến tiệc nào sẽ bỏ cuộc.

Sau mỗi đêm, đếm số bò tham dự mỗi loại tiệc (C, O, W).

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ (bạn thân)
Dòng 3: Số nguyên $M$
$M$ dòng tiếp theo: Số nguyên $c_{i}$ và ký tự $v_{i}$

Dữ liệu ra

$M$ dòng, mỗi dòng gồm 3 số nguyên: số bò tham dự tiệc C, O, W.

Ràng buộc

$1 \leq N, M \leq 2 \times 10^{5}$
$1 \leq a_{i} \leq N$ , $a_{i} \neq i$

Ví dụ

Input	Output	Giải thích
5 2 3 4 5 4 4 2 C 4 C 4 W 2 O	2 0 0 5 0 0 2 0 3 0 2 3	Đêm 1: bò 2 mở tiệc C, bò 1 theo bò 2. Đêm 2: bò 4 mở thêm tiệc C, tất cả đến tiệc C.

Bình luận

Không có bình luận tại thời điểm này.