CCAY - Chặt cây (Jakarta 2014 - E)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Cây (tree) trong lý thuyết đồ thị là một đồ thị liên thông không chu trình, rừng (forest) là tập hợp của một hay nhiều cây. Trong bài này, bạn được nhận một rừng (tạo thành từ các cây) gôm N nút và K truy vấn. Có 2 loại truy vấn:
• C x : Xóa cạnh nối giữa nút x và cha của nó. Nếu x không có cha (x là gốc), truy vấn này được bỏ qua.
• Q a b : Xuất ra "YES" nếu có một đường đi từ nút a đến nút b, ngược lại xuất ra "NO" (không có dấu ngoặc kép)

.Ví dụ: giả sử ta có một rừng như Hình 1 bên dưới:

Và danh sách các truy vấn theo thứ tự sau:

 - Q 5 7: xuất ra YES - đường đi: 5 - 2 - 1 - 3 - 7

 - C 2: xóa cạnh nối giữa 2 và 1, đồ thị trở thành Hình 2

 - Q 5 7: xuất ra NO - không còn đường đi từ 5 đến 7 nữa (theo Hình 2)

 - Q 4 6: xuất ra YES - đường đi: 4 - 2 - 6

Dữ liệu nhập: Dòng đầu tiên chứ một số nguyên T (0 < T ≤ 50), mỗi bộ test sẽ gồm nhiều dòng:

 - Dòng đầu tiên của mỗi bộ test chứ 2 số nguyên T và K (1 ≤ ≤ 20000, 1 ≤ 10000) - số nút của đồ thị và số lượng truy vấn.

 - Dòng tiếp theo chứ N số nguyên Pi, (0 ≤ Pi ≤ N), Pi là đỉnh cha của đỉnh i, nếu Pi = 0 thì đỉnh i là nút gốc của cây. Dữ liệu luôn đảm bảo rằng đây là một rừng.

 - Dòng thứ i trong K dòng tiếp theo, mỗi dòng là một tuy vấn, dạng "C x" hoặc "Q a b" (1 ≤ x, a, b ≤ N)

Dữ liệu xuất: với mỗi bộ test, xuất ra "Case #X:" trên dòng đầu tiên, trong đó X là số thứ tự của bộ test (bắt đầu từ 1). Với mỗi truy vấn "Q a b" xuất ra trên 1 dòng, "YES" hoặc "NO" (không có dấu ngoặc kép)

 

Ví dụ

  • input
    4
    7 4
    0 1 1 2 2 2 3
    Q 5 7
    C 2
    Q 5 7
    Q 4 6
    4 4
    2 0 2 3
    C 3
    Q 1 2
    C 1
    Q 1 2
    3 5
    0 3 0
    C 1
    Q 1 2
    C 3
    C 1
    Q 2 3
    1 1
    0
    Q 1 1
    output
    Case #1:
    YES
    NO
    YES
    Case #2:
    YES
    NO
    Case #3:
    NO
    YES
    Case #4:
    YES

Bộ test thứ hai (Hình 2)

 - C 3: xóa cạnh (3, 2) - kết quả thu được là đồ thị trong Hình 4

 - Q 1 2: kết quả là YES

 - C 1: xóa cạnh (1 , 2) - kết quả thu được là đồ thị trong Hình 5

 - Q 1 2: kết quả là NO

The 2014 ACM-ICPC Asia Jakarta Regional Contest - Problem E

Ghi chú: Vì kích thước file tối đa khi upload bị hạn chế nên không thể upload được bộ test có dữ liệu lớn, vì vậy bộ test được sử dụng ở đây không được sát với giới hạn đề bài. Bộ test có kích thước lớn nhất là gồm 21 test case, mỗi test case có N = 20000, K = 5000 (số lượnt test case tối đa là 50). Nên các bạn khi AC ở đây nhưng vẫn có thể bị TLE ở bộ test chuẩn hơn. Sau khi đã AC tại đây, các bạn có thể submit bài lên trang ACM-ICPC Live Archive với bộ test lớn hơn, sát với đề bài hơn để có thể biết được thuật toán của mình dùng đã có thể AC bài này thật sự chưa :D

Link: 6910 - Cutting Tree

Back to Top