Lại đồ thị

View as PDF

Submit solution

Points: 1.16 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Online Informatics Olympiad '09Day 1
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ngoài lề một tí

Nếu bạn là thí sinh thi VNOI OI'09, đọc đến đây chắc hẳn bạn đang mừng lắm. Bởi vì mãi mới tìm thấy bài đồ thị "tủ" để kiếm điểm. Chắc chắn bạn sẽ càng mừng hơn nếu như tôi nói với bạn rằng bài mà bạn chuẩn bị đọc ở đây không yêu cầu thuật toán đồ thị nào cả mà chỉ hỏi về phần mà ai cũng biết đó là biểu diễn đồ thị.

Đề bài

Chú ý: đồ thị trong bài này là đồ thị có hướng.

Bạn cần viết chương trình xử lý các yêu cầu sau:

  • NEW ~n~ ~k~, với ~k = 0~ hoặc ~k = 1~ (khởi tạo ~1~ đồ thị mới với ~n~ đỉnh, nếu ~k = 0~ thì là đồ thị rỗng, nếu ~k = 1~ thì là đồ thị đầy đủ, đồ thị đầy đủ này bao gồm ~n^{2}~ cạnh, nghĩa là bao gồm cả các vòng ~(u, u)~ với ~1 \leq u \leq n)~.
  • ADD ~u~ ~v~ (thêm cạnh ~(u, v)~ nếu chưa có).
  • DEL ~u~ ~v~ (xóa cạnh ~(u, v)~ nếu có).
  • ANY (xóa một cạnh bất kì trong đồ thị nếu có).
  • EDG ~u~ ~v~ (kiểm tra xem có cạnh ~(u, v)~ hay không).

Bạn hãy lập trình xử lý bài toán sau đây:

  • Nhập vào ~M~ yêu cầu, hãy thực hiện lần lượt từng yêu cầu.
  • Đối với những yêu cầu ANY, in ra cạnh bị xóa. Nếu không có cạnh nào thì in ra ~- 1~.
  • Đối với những yêu cầu EDG ~u~ ~v~, in ra YES/NO tương ứng với có hay không có cạnh ~(u, v)~.

Input

  • Gồm nhiều dòng, mỗi dòng ghi một yêu cầu cần xử lý. Dòng cuối cùng ghi "END" báo hiệu kết thúc dữ liệu. Số yêu cầu cần xử lý không quá ~10^{6}~.

Với yêu cầu dạng NEW, ta luôn có ~1 \leq n \leq 1000~.

Dữ liệu đảm bảo yêu cầu đầu tiên luôn là yêu cầu dạng NEW và với các yêu cầu ADD, DEL, EDG, ~1 \leq u~, ~v \leq n~.

Output

Tương ứng với mỗi yêu cầu dạng ANY hay EDG là một dòng ghi kết quả.

  • Đối với yêu cầu dạng ANY, ghi ra hai số ~u~, ~v~ cho biết bạn muốn xóa cạnh ~(u, v)~.
  • Đối với yêu cầu dạng EDG, ghi ra "YES" hoặc "NO" tương ứng với việc đồ thị còn cạnh ~(u, v)~ hay không.

Sample Input

NEW 4 0
ADD 1 2
ADD 2 3
ANY
EDG 1 2
END

Sample Output

1 2
NO

Note

Với test ví dụ ở trên, kết quả sau đây cũng hợp lệ:

2 3
YES

Comments

Please read the guidelines before commenting.



  • 2
    leduykhongngu  commented on Nov. 26, 2021, 5:20 a.m.

    Test bài này đã được cập nhật, cám ơn bạn water đã đóng góp test. Mình đã chấm lại và chỉ còn 4 submission AC (trước đó là 13).


    • 6
      water  commented on Nov. 26, 2021, 7:18 a.m.

      Dạ em cảm ơn anh ạ uwu


  • 0
    dlbm1302  commented on Sept. 29, 2021, 10:54 a.m. edited

    Em có một ý kiến đấy là main test của bài này hình như hơi yếu phải không ạ?