BOI 2015 - Ngày 2

Byteasar thích sống mạo hiểm. Anh chạy khi đang cầm kéo, nộp lời giải mà không thử các ví dụ, và muốn mọi tệp của mình có đường dẫn dài đúng bằng giới hạn hệ điều hành cho phép; chẳng hạn, trên Linux là \(4095\) ký tự.

Khi làm việc trên máy tính của người khác, Byteasar có thể gặp những tệp chưa đáp ứng tiêu chí đó. Anh sẽ thử thêm các liên kết tượng trưng, hay symlink, rồi dùng chúng để tạo đường dẫn. Với mỗi tệp trong hệ thống, hãy xác định liệu Byteasar có thể thêm một liên kết tượng trưng duy nhất, có độ dài tên được anh chọn trước, để tồn tại một đường dẫn dài đúng \(k\) ký tự trỏ đến tệp ấy hay không. Mỗi tệp được xét độc lập.

Nếu tệp có tên file nằm trong chuỗi thư mục dir1, dir2, ..., dirj, thì đường dẫn tuyệt đối của nó là /dir1/dir2/.../dirj/file. Thư mục gốc được biểu diễn bằng /; một tệp nằm trực tiếp trong thư mục gốc có đường dẫn tuyệt đối dạng /file.

Liên kết tượng trưng là một lối tắt có tên trỏ đến một thư mục, và có thể được đặt trong bất kỳ thư mục nào của hệ thống. Trong bài toán này, không được tạo liên kết tượng trưng trỏ đến tệp.

Nhờ liên kết tượng trưng, ta có thể tạo các đường dẫn khác nhau cùng trỏ đến một tệp. Ví dụ, nếu đặt một liên kết tên hello trỏ đến / ngay trong /, thì /dir/file, /hello/dir/file và /hello/hello/dir/file đều trỏ đến cùng một tệp nhưng có độ dài khác nhau. Tương tự, nếu đặt một liên kết tên hi trỏ đến / trong /dir, ta có các đường dẫn /dir/file, /dir/hi/dir/file và /dir/hi/dir/hi/dir/file.

Liên kết có thể trỏ lên trên, xuống dưới, sang một nhánh khác trong cây thư mục, hoặc trở lại chính thư mục chứa nó. Không được sử dụng các thành phần ./, ../ hoặc // trong đường dẫn.

Dữ liệu vào

Dòng đầu chứa ba số nguyên dương \(n,m,k\): số thư mục không kể thư mục gốc, số tệp, và độ dài đường dẫn mong muốn. Thư mục gốc mang số \(0\), các thư mục còn lại được đánh số từ \(1\) đến \(n\). Các tệp được đánh số từ \(1\) đến \(m\).

Dòng thứ hai chứa số nguyên \(s\), là độ dài tên của liên kết tượng trưng được thêm. Tên cụ thể không quan trọng; dữ liệu bảo đảm tên ấy không trùng với bất kỳ tên nào khác trong hệ thống tệp.

\(n\) dòng tiếp theo mô tả các thư mục không kể thư mục gốc. Dòng thứ \(i\) trong số đó chứa hai số nguyên \(p_i,l_i\), cho biết thư mục \(i\) có tên dài \(l_i\) ký tự và nằm trực tiếp trong thư mục \(p_i\). Dữ liệu bảo đảm \(p_i<i\).

Cuối cùng là \(m\) dòng mô tả các tệp. Dòng thứ \(j\) trong số đó chứa hai số nguyên \(p_j,l_j\), cho biết tệp \(j\) có tên dài \(l_j\) ký tự và nằm trực tiếp trong thư mục \(p_j\).

Tên của mọi tệp và thư mục đều có độ dài dương. Các đường dẫn tuyệt đối ban đầu của chúng đều dài không quá \(k\) ký tự.

Dữ liệu ra

In \(m\) dòng, mỗi dòng ứng với một tệp. Dòng thứ \(j\) chứa YES nếu có thể thêm một liên kết tượng trưng có tên dài \(s\) ký tự để tạo ra một đường dẫn dài đúng \(k\) ký tự trỏ đến tệp \(j\); ngược lại, in NO.

Ràng buộc

• \(1\le n,m\le3000\).
• \(1\le k,s\le1\,000\,000\).
• Với thư mục \(i\), \(0\le p_i<i\) và \(l_i\ge1\).
• Với tệp \(j\), \(0\le p_j\le n\) và \(l_j\ge1\).
• Độ dài đường dẫn tuyệt đối ban đầu của mọi tệp và thư mục không vượt quá \(k\).

Phân nhóm

1. 33 điểm: \(n,m\le500\).
2. 33 điểm: \(n,m\le3000\); với mỗi tệp có đáp án YES, tồn tại cách thêm một liên kết tượng trưng và một đường dẫn dài đúng \(k\) đến tệp đó mà chỉ cần đi qua liên kết này nhiều nhất một lần.
3. 34 điểm: \(n,m\le3000\).

Ví dụ

2 4 22
2
0 1
1 5
2 13
2 10
1 4
0 7

YES
YES
YES
NO

Byteasar là một hacker đã giành quyền tham dự IHO, Olympic Tin tặc Quốc tế, năm nay. Một bài thi yêu cầu anh đối đầu với người quản trị hệ thống. Có \(n\) máy tính được đánh số từ \(1\) đến \(n\), nối thành một vòng: máy tính \(i\) nối với máy tính \(i+1\) với mọi \(i=1,\ldots,n-1\), và máy tính \(n\) nối với máy tính \(1\).

Cuộc đấu là một trò chơi giữa Byteasar và người quản trị với các quy tắc sau:

• Byteasar đi trước. Sau đó, người quản trị và Byteasar lần lượt thực hiện các lượt đi xen kẽ.
• Trong lượt đi đầu tiên của mình, Byteasar chọn một máy tính bất kỳ và xâm nhập nó, chẳng hạn bằng cách khai thác lỗ hổng của hệ điều hành.
• Trong lượt đi đầu tiên của mình, người quản trị chọn một máy tính chưa bị xâm nhập và bảo vệ nó, chẳng hạn bằng cách cài các bản cập nhật bảo mật mới nhất.
• Trong mỗi lượt đi tiếp theo, Byteasar có thể không làm gì, hoặc chọn một máy tính chưa bị xâm nhập cũng chưa được bảo vệ, có kết nối trực tiếp với một máy tính đã bị xâm nhập, rồi xâm nhập máy tính được chọn.
• Trong mỗi lượt đi tiếp theo, người quản trị có thể không làm gì, hoặc chọn một máy tính chưa bị xâm nhập cũng chưa được bảo vệ, có kết nối trực tiếp với một máy tính đã được bảo vệ, rồi bảo vệ máy tính được chọn.
• Trò chơi kết thúc ngay khi cả hai người đều không làm gì trong hai lượt đi liên tiếp.

Ban đầu, chưa có máy tính nào bị xâm nhập hoặc được bảo vệ.

Máy tính \(i\) có giá trị \(v_i\), biểu thị giá trị dữ liệu được lưu trên nó. Với mỗi máy tính \(i\) xâm nhập được, Byteasar nhận \(v_i\) điểm. Anh là một hacker khá giỏi nhưng không biết về thuật toán, nên nhờ bạn viết chương trình tính số điểm lớn nhất anh có thể đạt được khi người quản trị chơi tối ưu.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(n\ge2\)), là số máy tính.

Dòng thứ hai chứa \(n\) số nguyên \(v_1,v_2,\ldots,v_n\) (\(1\le v_i\le2000\)), trong đó \(v_i\) là giá trị dữ liệu trên máy tính \(i\).

Dữ liệu ra

In một số nguyên duy nhất là số điểm lớn nhất Byteasar có thể đạt được khi đối đầu với người quản trị chơi tối ưu.

Ràng buộc

• \(2\le n\le500\,000\).
• \(1\le v_i\le2000\) với mọi \(1\le i\le n\).

Phân nhóm

1. 20 điểm: \(n\le300\).
2. 20 điểm: \(n\le5000\).
3. 20 điểm: \(n\le500\,000\) và xâm nhập máy tính \(1\) là một lựa chọn tối ưu cho lượt đi đầu tiên của Byteasar.
4. 40 điểm: \(n\le500\,000\).

Ví dụ

4
7 6 8 4

13

5
1 1 1 1 1

3

Kéo co là môn thể thao rất phổ biến ở Byteland. Luật chơi rất đơn giản: hai đội kéo một sợi dây theo hai hướng ngược nhau. Giải kéo co từ thiện hằng năm của Byteland đang diễn ra và có rất nhiều người đăng ký. Với vai trò phụ trách tính công bằng, bạn cần chia những người tham gia thành hai đội để trận đấu có thể kéo dài.

Có tổng cộng \(2n\) người đăng ký, nên mỗi đội sẽ có \(n\) người. Sợi dây có \(n\) vị trí ở bên trái và \(n\) vị trí ở bên phải. Những tay kéo co hàng đầu Byteland khá kén chọn: mỗi người chỉ chấp nhận đúng một vị trí bên trái và đúng một vị trí bên phải. Bạn cũng biết sức mạnh của từng người.

Ban tổ chức đưa ra một số nguyên \(k\) và hỏi: có thể chia thành hai đội, mỗi đội có \(n\) người, sao cho mỗi người đứng ở một trong hai vị trí mình chấp nhận, không có hai người đứng cùng một vị trí, và tổng sức mạnh của hai đội chênh lệch không quá \(k\) hay không?

Dữ liệu vào

Dòng đầu chứa số nguyên dương \(n\), là số vị trí ở mỗi bên sợi dây, và số nguyên \(0\le k\le20n\), là độ chênh lệch sức mạnh tối đa được phép. Những người tham gia được đánh số từ \(1\) đến \(2n\).

Mỗi dòng trong \(2n\) dòng tiếp theo mô tả một người. Dòng thứ \(i\) chứa ba số nguyên dương \(l_i,r_i,s_i\) (\(1\le l_i,r_i\le n\), \(1\le s_i\le20\)), cho biết người \(i\) có sức mạnh \(s_i\) và muốn đứng ở vị trí \(l_i\) bên trái hoặc vị trí \(r_i\) bên phải sợi dây.

Dữ liệu ra

In YES nếu có thể tạo hai đội thỏa mãn tất cả các yêu cầu trên; ngược lại, in NO. Kết quả được in trên một dòng duy nhất.

Ràng buộc

• \(1\le n\le30\,000\).
• \(k\) là số nguyên và \(0\le k\le20n\).
• \(1\le l_i,r_i\le n\) và \(1\le s_i\le20\) với mọi \(1\le i\le2n\).

Phân nhóm

1. 18 điểm: \(n\le10\).
2. 30 điểm: \(n\le2000\).
3. 23 điểm: \(n\le30\,000\) và \(s_i=1\) với mọi \(1\le i\le2n\).
4. 29 điểm: \(n\le30\,000\).

Ví dụ

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

YES

2 5
1 1 1
1 2 4
2 2 1
2 1 4

NO