NUMLAND - Numberland
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

Đề thi tuyển quân ACM ICPC Đại học Khoa học Tự nhiên TPHCM 2014 - Round 1 (Single)

Trong đất nước Numberland có N thành phố được đánh số từ 1 đến N và N con đường hai chiều nối giữa các thành phố. Mỗi con đường nối giữa hai thành phố. Từ một thành phố có thể đi đến bất kì thành phố khác thông qua các con đường nối giữa chúng. Có 2 dân tộc đang sinh sống trong N thành phố này, dân tộc Binariers - dùng hệ đếm nhị phân và Decimalers - dùng hệ đếm thập phân. Và vì việc sử dụng 2 hệ đếm khác nhau và dân tộc nào cũng muốn hệ đếm của mình là hệ đếm chính thức của đất nước Numberland cho nên chiến tranh đã xảy ra.

Sau một thời gian dài chiến tranh, cả 2 dân tộc quyết định là sẽ dừng cuộc chiến lại. Mỗi dân tộc sẽ chọn ra một "City-line". Một City-line sẽ bao gồm 2 thành phố mút u, v và tập hợp các thành phố nằm trên đường đi ngắn nhất từ u đến v (bao gồm cả u và v), mỗi thành phố xuất hiện nhiều nhất một lần.

Nhưng nếu 2 City-line được chọn bởi 2 dân tộc có va chạm với nhau, tức là sẽ tồn tại một số thành phố mà nó vừa thuộc City-line của dân tộc Binariers vừa thuộc City-line của dân tộc Decimalers, cả 2 sẽ cảm thấy khó chịu, không bên nào muốn nhường bên nào và khi đó, chiến tranh sẽ nổ ra một lần nữa.

Nhiệm vụ của bạn là với 2 City-line được chọn bởi 2 dân tộc, hãy cho biết hòa bình có được thiết lập hay không hay chiến tranh sẽ nổ ra một lần nữa trên đất nước Numberland.

Dữ liệu nhập:

 - Dòng đầu tiên chứa 2 số nguyên dương N, Q - số thành phố của Numberland và số lượng truy vấn. (1 ≤ N, M ≤ 105)

 - Dòng thứ i trong N - 1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương u, v - con đường nối giữa 2 thành phố u và v (1 ≤ u, v ≤ 105, u ≠ v)

 - Q dòng tiếp theo, mỗi dòng chứa 4 số nguyên u, v, x, y - u, v là 2 thành phố mút trên City-line của dân tộc Binariers và x, y là 2 thành phố mút trên City-line của dân tộc Decimalers.

Ví dụ

  • input
    5 3
    1 2
    1 3
    3 4
    3 5
    1 3 4 5
    1 2 4 5
    1 5 2 4
    output
    war again
    peace
    war again

Trong bộ test thứ nhất:

 - Truy vấn 1: đường đi ngắn nhất từ 1 đến 3 là {1, 3}, đường đi ngắn nhất từ 4 đến 5 là {4, 3, 5}, như vậy thành phố 3 thuộc cả 2 City-line, kết quả là war again.

 - Truy vấn 2: đường đi ngắ nhất từ 1 đến 2: {1, 2}, đườn đi ngắn nhất từ 4 đến 5: {4, 3, 5}, kết quả là peace

 - Truy vấn 3: đường đi ngắ nhất từ 1 đến 5: {1, 3, 5}, đường đi ngắn nhất từ 2 đến 4: {2, 1, 3, 4}, kết quả là war again

 

Back to Top