JOI 2010 Final Camp - Ngày 4

Trên thế giới có vô số cuộc thi lập trình: từ những cuộc thi mà người tham gia tranh tài với các đối thủ trên khắp thế giới như Olympic Tin học, ACM-ICPC và ICFP, đến các cuộc thi trong nước Nhật Bản như Supercomputing Contest, Cuộc thi Máy tính Koshien và EPOCH tại Matsuyama.

Sau khi tham gia những cuộc thi như vậy, một số người muốn tự tổ chức một cuộc thi. Bạn của bạn cũng là một người như thế. Vì bận chuẩn bị đề thi, người bạn ấy nhờ bạn viết chương trình tính điểm của các thí sinh từ nhật ký cuộc thi. Hãy viết một chương trình tính điểm chính xác để góp phần giúp cuộc thi của bạn mình thành công.

Cuộc thi có \(N\) thí sinh, \(M\) bài toán và kéo dài \(T\) giây. Các thí sinh được đánh số từ \(1\) đến \(N\), còn các bài toán được đánh số từ \(1\) đến \(M\).

Với mỗi bài toán, thí sinh xem đề, giải bài rồi nộp mã nguồn lời giải. Cuộc thi bắt đầu ở thời điểm \(0\) và kết thúc ở thời điểm \(T\). Khi một thí sinh xem đề, thời điểm, số hiệu thí sinh và số hiệu bài toán được ghi thành một bản ghi trong nhật ký. Khi một thí sinh nộp mã nguồn lời giải, thời điểm, số hiệu thí sinh, số hiệu bài toán và kết quả đúng hay sai của mã nguồn được ghi thành một bản ghi trong nhật ký.

Kể từ khi cuộc thi bắt đầu, mỗi giây, mỗi thí sinh có thể thực hiện một lần một trong hai thao tác: xem đề của một bài toán hoặc nộp mã nguồn cho một bài toán. Thí sinh không thể nộp mã nguồn cho một bài toán trước khi xem đề của bài đó, cũng không thể nộp thêm mã nguồn cho bài đó sau khi đã nộp đúng.

Giả sử thí sinh \(j\) xem đề bài \(i\) ở thời điểm \(S_{ij}\), nộp sai \(w_{ij}\) lần rồi nộp đúng ở thời điểm \(E_{ij}\). Điểm của thí sinh đó cho bài toán này là

Ở đây, \(p_i\) là số điểm của bài \(i\), còn \(X\) là điểm tối thiểu khi giải đúng một bài, không phụ thuộc vào số hiệu bài toán. Nếu đến khi cuộc thi kết thúc mà thí sinh chưa nộp đúng một bài thì điểm của bài đó là \(0\). Tổng điểm của một thí sinh là tổng điểm của thí sinh đó trên tất cả các bài toán.

Yêu cầu

Cho \(N\), \(M\), \(T\), \(X\), số bản ghi trong nhật ký, số điểm của từng bài toán và nội dung nhật ký, hãy viết chương trình tính tổng điểm của từng thí sinh.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa năm số nguyên \(N\), \(M\), \(T\), \(X\), \(Y\), cách nhau bởi dấu cách, lần lượt là số thí sinh, số bài toán, thời gian thi, điểm tối thiểu của một bài giải đúng và số bản ghi trong nhật ký.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(p_i\), là số điểm của bài toán \(i\).
• Trong \(Y\) dòng tiếp theo, dòng thứ \(k\) mô tả bản ghi thứ \(k\) của nhật ký, gồm số nguyên \(t_k\) chỉ thời điểm ghi nhận, số nguyên \(n_k\) chỉ số hiệu thí sinh, số nguyên \(m_k\) chỉ số hiệu bài toán và một trong ba chuỗi open, correct, incorrect, cách nhau bởi dấu cách.

Chuỗi open cho biết thí sinh đã xem đề; correct cho biết mã nguồn đã nộp là đúng; incorrect cho biết mã nguồn đã nộp là sai.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(j\) chứa tổng điểm của thí sinh số \(j\).

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le 1\,000\).

• \(1\le M\le 10\).
• \(100\le T\le 10\,000\).
• \(1\le X\le 100\).
• \(0\le Y\le 10\,000\).
• \(X\le p_i\le T\) với mọi \(1\le i\le M\).
• Các thời điểm trong nhật ký là số nguyên và thỏa mãn \(0\le t_1\le t_2\le\cdots\le t_Y\le T\).
• \(1\le n_k\le N\) và \(1\le m_k\le M\) với mọi \(1\le k\le Y\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

Ví dụ

1 3 1200 30 8
50
1000
800
0 1 1 open
100 1 2 open
400 1 1 correct
500 1 2 incorrect
600 1 2 correct
700 1 3 open
800 1 3 incorrect
900 1 3 incorrect

410

3 2 1000 10 10
878
712
0 2 1 open
0 1 1 open
0 3 1 open
100 3 1 correct
100 2 1 correct
100 1 2 open
200 2 2 open
200 1 2 incorrect
300 1 2 correct
300 2 2 correct

392
1390
778

Canada có \(N\) thành phố được đánh số từ \(1\) đến \(N\) và \(N-1\) đường cao tốc được đánh số từ \(1\) đến \(N-1\). Mỗi đường cao tốc nối hai thành phố và có thể đi theo cả hai chiều. Mạng lưới đường cao tốc được thiết kế sao cho có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác bằng cách đi qua một số đường cao tốc. Nói cách khác, \(N\) thành phố và \(N-1\) đường cao tốc tạo thành một cây.

Bạn được bổ nhiệm làm giám đốc trung tâm thông tin ùn tắc giao thông và phải quản lý thông tin ùn tắc của mạng lưới đường cao tốc này.

Với mỗi đường trong số \(N-1\) đường cao tốc, trung tâm quản lý thời gian cần để đi từ thành phố ở đầu này đến thành phố ở đầu kia theo từng chiều. Chẳng hạn, trong hình dưới đây, các cặp thành phố \(1\) và \(3\), \(3\) và \(4\), \(2\) và \(3\) được nối bằng đường cao tốc. Trung tâm quản lý thời gian đi từ thành phố \(i\) đến thành phố \(j\) cho từng cặp sau:

Lưu ý rằng thời gian đi theo hai chiều của cùng một đường cao tốc không nhất thiết bằng nhau.

Ngoài việc lưu trữ dữ liệu, trung tâm còn thực hiện hai công việc sau.

Thỉnh thoảng, trung tâm nhận được một bản tin ùn tắc gồm ba số nguyên dương \(r\), \(s\), \(t\). Bản tin này cho biết thời gian đi theo chiều thuận của đường cao tốc \(r\) là \(s\), còn thời gian đi theo chiều ngược là \(t\). Chiều thuận là chiều đi từ thành phố có số hiệu nhỏ hơn đến thành phố có số hiệu lớn hơn trong hai đầu của đường cao tốc; chiều ngược là chiều còn lại. Trung tâm cập nhật dữ liệu theo bản tin này.

Trung tâm cũng có thể nhận được một cuộc gọi hỏi thông tin, được biểu diễn bởi hai số nguyên dương \(x\), \(y\). Khi đó, dựa trên dữ liệu hiện tại, trung tâm phải tính và trả lời thời gian cần để đi từ thành phố \(x\) đến thành phố \(y\).

Yêu cầu

Cho dãy các bản tin ùn tắc và yêu cầu hỏi thông tin trong một ngày, gọi chung là các truy vấn, theo thứ tự thời gian. Hãy viết chương trình in đáp án cho từng yêu cầu hỏi thông tin. Trước khi nhận bản tin ùn tắc đầu tiên, thời gian đi theo mỗi chiều của tất cả \(N-1\) đường cao tốc đều bằng \(1\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách. \(M\) là tổng số bản tin ùn tắc và yêu cầu hỏi thông tin.
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(p_i\), \(q_i\), cách nhau bởi dấu cách, cho biết đường cao tốc \(i\) nối thành phố \(p_i\) và thành phố \(q_i\).
• Mỗi dòng trong \(M\) dòng tiếp theo mô tả một truy vấn theo một trong hai dạng I r s t hoặc Q x y, với các thành phần cách nhau bởi dấu cách.

Truy vấn I r s t là bản tin ùn tắc: cập nhật thời gian đi theo chiều thuận của đường cao tốc \(r\) thành \(s\) và theo chiều ngược thành \(t\). Truy vấn Q x y yêu cầu thời gian đi từ thành phố \(x\) đến thành phố \(y\); hai thành phố này khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn số dòng bằng số truy vấn Q trong dữ liệu vào. Dòng thứ \(i\) chứa một số nguyên là đáp án cho yêu cầu hỏi thông tin thứ \(i\).

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(4\) giây, bộ nhớ \(256\) MB.

• \(2\le N\le 100\,000\).

• \(1\le M\le 100\,000\).
• \(1\le p_i<q_i\le N\) với mọi \(1\le i\le N-1\).
• Các thành phố và đường cao tốc tạo thành một cây.
• Trong mỗi truy vấn I r s t: \(1\le r\le N-1\), \(1\le s\le 1\,000\), \(1\le t\le 1\,000\).
• Trong mỗi truy vấn Q x y: \(1\le x,y\le N\) và \(x\ne y\).

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(16\) nhóm kiểm thử, mỗi nhóm \(5\) điểm và chứa \(1\) bộ dữ liệu, cùng \(2\) nhóm kiểm thử, mỗi nhóm \(10\) điểm và chứa \(2\) bộ dữ liệu. Có tất cả \(20\) bộ dữ liệu. Chỉ nhận điểm của một nhóm khi chương trình cho kết quả đúng trên tất cả các bộ dữ liệu trong nhóm, kết thúc bình thường (trả về mã \(0\)) và tuân thủ giới hạn thời gian, bộ nhớ.

• Các bộ kiểm thử có tổng cộng \(20\) điểm thỏa mãn \(N\le 1\,000\) và \(M\le 1\,000\).
• Các bộ kiểm thử có tổng cộng \(50\) điểm thỏa mãn: từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác đều có thể đi qua không quá \(1\,000\) đường cao tốc.

Ví dụ

4 5
1 3
3 4
2 3
I 1 7 9
Q 2 4
I 3 12 11
Q 2 4
Q 4 2

2
13
12

Ở phía đông nam Canada, tại khu vực biên giới với Hoa Kỳ, có năm hồ nổi tiếng được gọi chung là Ngũ Đại Hồ. Nhân dịp IOI được tổ chức tại Canada, nhiều kế hoạch khai thác thuyền du lịch trên hồ Ontario, hồ gần địa điểm tổ chức nhất, đã được đề xuất.

Mỗi kế hoạch khai thác thuyền du lịch nối hai điểm trên bờ hồ. Có tất cả \(N\) kế hoạch; kế hoạch thứ \(i\) cho thuyền hoạt động giữa điểm \(s_i\) và điểm \(t_i\). Ở đây, điểm \(x\) là điểm đạt được khi xuất phát từ điểm cực đông của hồ rồi đi dọc theo bờ hồ ngược chiều kim đồng hồ một quãng đường \(x\) mét. Chiều dài một vòng bờ hồ là \(500\,000\) mét.

Người ta muốn thực hiện càng nhiều kế hoạch càng tốt. Tuy nhiên, để tránh các thuyền va chạm nhau, không được có hai tuyến thuyền giao nhau.

Yêu cầu

Cho \(N\) kế hoạch khai thác thuyền, hãy viết chương trình tìm số kế hoạch lớn nhất có thể thực hiện.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa số nguyên \(N\), là số kế hoạch khai thác thuyền du lịch.
• Dòng thứ \(i+1\) với \(1\le i\le N\) chứa hai số nguyên \(s_i\), \(t_i\), cách nhau bởi dấu cách, là hai điểm được nối trong kế hoạch thứ \(i\).

Tất cả \(2N\) giá trị \(s_1,\ldots,s_N,t_1,\ldots,t_N\) đều khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số kế hoạch lớn nhất có thể thực hiện trong các kế hoạch đã cho.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(256\) MB.

• \(1\le N\le 2\,000\).

• \(0\le s_i<500\,000\) và \(0\le t_i<500\,000\) với mọi \(1\le i\le N\).
• Tất cả \(2N\) tọa độ đầu mút đều khác nhau.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ kiểm thử có tổng cộng \(40\) điểm thỏa mãn \(N\le 200\).

Ví dụ

5
50000 150000
450000 100000
200000 300000
260000 350000
0 230000

3

Ở đất nước JOI có \(N\) công ty sản xuất phích cắm điện. Mỗi công ty được cấp một mã số nguyên từ \(1\) đến \(N\). Mỗi công ty sản xuất một kiểu phích cắm cùng ổ cắm tương ứng, nhưng điều phiền phức là phích cắm và ổ cắm của mỗi công ty lại có hình dạng khác với của tất cả các công ty khác.

Luật của JOI quy định rằng ổ cắm phải được in mã công ty sản xuất, còn trên phích cắm thì không có mã công ty. Để có thể đáp ứng nhanh yêu cầu của khách hàng trong hoàn cảnh đó, chủ một cửa hàng đồ điện có một hộp dụng cụ chứa đủ \(N\) loại phích cắm có ở JOI, mỗi loại một chiếc, được xếp theo thứ tự mã công ty. Tuy nhiên, một ngày nọ, ông vô tình làm các phích cắm trong hộp bị xáo trộn. Ông có thể nhận ra rằng một loại phích cắm nào đó không cắm vừa một loại ổ cắm nào đó, nhưng không thể chỉ nhìn phích cắm mà biết công ty sản xuất. Vì vậy, ông không thể xếp lại các phích cắm như cũ. Cuối cùng, trong lúc hết sức bối rối, ông nhờ giáo sư L, người nổi tiếng có thể dễ dàng giải quyết mọi bài toán khó.

Để tiện phân biệt, giáo sư L đánh số các phích cắm đã bị xáo trộn từ \(1\) đến \(N\), rồi dựa trên cách đánh số đó thu thập \(M\) lời khẳng định từ người chủ cửa hàng. Lời khẳng định thứ \(k\) là: “Không phích cắm nào mang số từ \(C_k\) đến \(D_k\) cắm vừa bất kỳ ổ cắm nào có mã công ty từ \(A_k\) đến \(B_k\).” Các khoảng này đều bao gồm cả hai đầu mút.

Sau đó, giáo sư L nói: “Bí ẩn đã được giải quyết. Chỉ có duy nhất một cách ghép các phích cắm với công ty sản xuất thỏa mãn \(M\) lời khẳng định này. Phần còn lại ta giao cho con.” Rồi giáo sư ra về. Dù việc này thật vô lý, bạn, người học trò của giáo sư, phải giải quyết bài toán và cho chủ cửa hàng biết phích cắm nào do công ty nào sản xuất.

Yêu cầu

Hãy viết chương trình xác định sự tương ứng giữa các phích cắm và công ty sản xuất dựa trên những lời khẳng định của chủ cửa hàng.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• Trong \(M\) dòng tiếp theo, dòng thứ \(k\) mô tả lời khẳng định thứ \(k\), gồm bốn số nguyên \(A_k\), \(B_k\), \(C_k\), \(D_k\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(N\) dòng. Dòng thứ \(i\) chứa số hiệu của phích cắm do công ty có mã \(i\) sản xuất.

Ràng buộc

• Giới hạn trong kỳ thi gốc: thời gian \(1\) giây, bộ nhớ \(64\) MB.

• \(1\le N\le 3\,000\).

• \(1\le M\le 100\,000\).
• \(1\le A_k\le B_k\le N\) và \(1\le C_k\le D_k\le N\) với mọi \(1\le k\le M\).
• Có duy nhất một cách ghép tương ứng giữa \(N\) phích cắm và \(N\) công ty thỏa mãn tất cả \(M\) lời khẳng định.

Phân nhóm

Bài này có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ kiểm thử có tổng cộng \(20\) điểm thỏa mãn \(N\le 100\) và \(M\le 100\).

Ví dụ

3 2
1 1 2 3
1 2 3 3

1
2
3

8 7
2 4 2 3
4 7 1 2
6 8 1 4
3 4 3 5
5 6 6 8
6 7 6 7
7 8 6 6

2
4
1
6
3
5
8
7