JOI 2019 - Trại huấn luyện, ngày 3 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2019 - Designated Cities	100 (p)	2.0s	512M
2	JOI 2019 - Lamps	100 (p)	1.0s	256M
3	JOI 2019 - Bitaro, who Leaps through Time	100 (p)	3.0s	512M

1. JOI 2019 - Designated Cities

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Đất nước JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, được đánh số từ \(1\) đến \(N-1\). Đường thứ \(i\) có hai làn: một làn đi từ thành phố \(A_i\) đến thành phố \(B_i\) và một làn đi theo chiều ngược lại. Như vậy, mọi con đường đều đi được theo hai chiều. Có thể đi giữa hai thành phố bất kỳ bằng các con đường này.

Hiện tại, chưa có làn đường nào được trải nhựa. Trên đường thứ \(i\), chi phí trải nhựa làn từ \(A_i\) đến \(B_i\) là \(C_i\), còn chi phí trải nhựa làn từ \(B_i\) đến \(A_i\) là \(D_i\).

Ông K, thủ tướng đất nước JOI, có thể chọn một số thành phố để chỉ định làm thành phố nghỉ dưỡng. Khi thành phố \(x\) được chỉ định, với mỗi đường thứ \(i\), điều sau sẽ xảy ra: trong hai thành phố \(A_i\) và \(B_i\), gọi thành phố gần \(x\) hơn là \(a\), thành phố xa \(x\) hơn là \(b\). Ở đây, gần hơn có nghĩa là cần đi qua ít con đường hơn để đến \(x\). Khi đó, làn đường từ \(b\) đến \(a\) sẽ được trải nhựa nếu làn đó chưa được trải nhựa.

Chi phí trải nhựa các làn đường do việc chỉ định thành phố nghỉ dưỡng sẽ được chi trả bằng tiền thuế. Tuy nhiên, ông K phải dùng tiền túi của mình để trải nhựa tất cả các làn đường vẫn chưa được trải nhựa sau khi việc chỉ định kết thúc.

Có \(Q\) phương án được đề xuất. Trong phương án thứ \(j\), xuất phát từ trạng thái chưa có thành phố nghỉ dưỡng và chưa có làn đường nào được trải nhựa, ông K sẽ chỉ định đúng \(E_j\) thành phố làm thành phố nghỉ dưỡng. Những thành phố cụ thể chưa được chọn. Với mỗi phương án, hãy tính tổng chi phí nhỏ nhất mà ông K phải tự chi trả.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N
A_1 B_1 C_1 D_1
...
A_{N-1} B_{N-1} C_{N-1} D_{N-1}
Q
E_1
...
E_Q

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa tổng chi phí nhỏ nhất ông K phải tự chi trả trong phương án thứ \(j\).

Ràng buộc

\(2 \le N \le 200\,000\).
\(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\) với \(1 \le i \le N-1\).
Có thể đi giữa hai thành phố bất kỳ bằng các con đường đã cho.
\(1 \le C_i,D_i \le 1\,000\,000\,000\) với \(1 \le i \le N-1\).
\(1 \le Q \le N\).
\(1 \le E_j \le N\) với \(1 \le j \le Q\).

Phân nhóm

\(6\) điểm: \(N \le 16\).
\(7\) điểm: \(Q=1\) và \(E_1=1\).
\(9\) điểm: \(Q=1\) và \(E_1=2\).
\(17\) điểm: \(N \le 2\,000\).
\(17\) điểm: \(Q=1\).
\(44\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

9
1

Giải thích

Xét phương án thứ nhất: ông K chỉ định đúng một thành phố nghỉ dưỡng. Nếu chọn thành phố \(1\), các làn từ \(2\) đến \(1\) trên đường \(1\), từ \(3\) đến \(1\) trên đường \(2\), và từ \(4\) đến \(1\) trên đường \(3\) sẽ được trải nhựa. Các làn còn lại là từ \(1\) đến \(2\), từ \(1\) đến \(3\), và từ \(1\) đến \(4\), với tổng chi phí \(1+3+5=9\). Không có cách chọn một thành phố nào làm tổng chi phí này nhỏ hơn \(9\), nên đáp án là \(9\).

Xét phương án thứ hai: ông K chỉ định đúng hai thành phố nghỉ dưỡng. Nếu chọn thành phố \(3\) và \(4\), chỉ có làn từ \(1\) đến \(2\) trên đường \(1\) chưa được trải nhựa. Chi phí trải nhựa làn này là \(1\). Không có cách chọn hai thành phố nào làm chi phí nhỏ hơn \(1\), nên đáp án là \(1\).

Ví dụ 2

Input

Output

Giải thích

Ví dụ này thỏa mãn các ràng buộc của nhóm \(2\).

Ví dụ 3

Input

Output

Giải thích

Ví dụ này thỏa mãn các ràng buộc của nhóm \(3\).

Ví dụ 4

Input

15
14 5 12 7
14 12 6 5
14 10 14 16
9 14 16 12
13 7 4 15
1 3 8 1
6 7 15 13
15 4 4 6
9 1 12 6
13 1 7 6
13 4 5 15
2 6 11 19
8 4 12 7
13 11 14 5
3
3
6
7

Output

44
12
6

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 3 (22/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.

2. JOI 2019 - Lamps

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Có \(N\) bóng đèn xếp thành một hàng trong một hành lang dài, được đánh số từ \(1\) đến \(N\). Mỗi bóng đèn ở một trong hai trạng thái: tắt hoặc bật. Một cơ chế đặc biệt cho phép thay đổi trạng thái của các bóng đèn. Trong một thao tác, bạn có thể thực hiện một trong các việc sau:

Chọn hai số nguyên \(p,q\) thỏa mãn \(1 \le p \le q \le N\) và tắt tất cả các bóng đèn \(p,p+1,\ldots,q\).
Chọn hai số nguyên \(p,q\) thỏa mãn \(1 \le p \le q \le N\) và bật tất cả các bóng đèn \(p,p+1,\ldots,q\).
Chọn hai số nguyên \(p,q\) thỏa mãn \(1 \le p \le q \le N\) và đảo trạng thái của tất cả các bóng đèn \(p,p+1,\ldots,q\): bóng đang tắt chuyển thành bật, bóng đang bật chuyển thành tắt.

Trạng thái hiện tại được biểu diễn bằng xâu \(A\) có độ dài \(N\). Ký tự thứ \(i\) của \(A\) là 0 nếu bóng đèn \(i\) đang tắt, và là 1 nếu bóng đèn đó đang bật. Bạn muốn đưa các bóng đèn về trạng thái được biểu diễn bằng xâu \(B\) có độ dài \(N\), sử dụng ít thao tác nhất có thể. Ký tự thứ \(i\) của \(B\) là 0 nếu bóng đèn \(i\) cần tắt, và là 1 nếu bóng đèn đó cần bật.

Hãy tính số thao tác ít nhất cần thực hiện để đạt được trạng thái mong muốn.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
A
B

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số thao tác ít nhất cần thực hiện.

Ràng buộc

\(1 \le N \le 1\,000\,000\).
\(A\) và \(B\) là hai xâu có độ dài \(N\).
Mỗi ký tự của \(A\) và \(B\) là 0 hoặc 1.

Phân nhóm

\(6\) điểm: \(N \le 18\).
\(41\) điểm: \(N \le 2\,000\).
\(4\) điểm: Mọi ký tự của \(A\) đều là 0.
\(49\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

8
11011100
01101001

Output

Giải thích

Có thể đạt trạng thái mong muốn bằng bốn thao tác như sau:

Đảo trạng thái các bóng đèn \(1,2,3,4\). Xâu trạng thái trở thành 00101100.
Bật bóng đèn \(2\). Xâu trạng thái trở thành 01101100.
Đảo trạng thái các bóng đèn \(6,7,8\). Xâu trạng thái trở thành 01101011.
Tắt các bóng đèn \(6,7\). Xâu trạng thái trở thành 01101001.

Không thể đạt trạng thái mong muốn bằng ít hơn bốn thao tác, nên cần in ra \(4\).

Ví dụ 2

Input

13
1010010010100
0000111001011

Output

Ví dụ 3

Input

18
001100010010000110
110110001000100101

Output

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 3 (22/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.

3. JOI 2019 - Bitaro, who Leaps through Time

Điểm: 100 (p) Thời gian: 3.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Beaverland có \(N\) thành phố, được đánh số từ \(1\) đến \(N\), và \(N-1\) con đường nối các thành phố. Đường thứ \(i\) nối thành phố \(i\) với thành phố \(i+1\) theo cả hai chiều.

Ở Beaverland, đơn vị thời gian là Byou. Mỗi ngày dài \(1\,000\,000\,000\) Byou. Thời điểm cách đầu ngày \(x\) Byou, với \(0 \le x < 1\,000\,000\,000\), được gọi là thời điểm \(x\). Đi qua bất kỳ con đường nào cũng mất \(1\) Byou. Mỗi ngày, đường thứ \(i\) chỉ có thể được đi qua trong khoảng từ thời điểm \(L_i\) đến thời điểm \(R_i\). Cụ thể, để đi qua đường này, phải rời thành phố \(i\) hoặc \(i+1\) tại thời điểm \(x\) thỏa mãn \(L_i \le x \le R_i-1\) và đến thành phố còn lại tại thời điểm \(x+1\).

Bitaro vốn là một chú hải ly bình thường sống ở Beaverland. Tuy nhiên, trong lúc tìm cách đối phó với việc đi muộn, cậu đã có được khả năng quay ngược thời gian. Mỗi lần sử dụng khả năng này, cậu quay lại thời điểm cách đó \(1\) Byou. Cậu không thể quay về ngày trước: nếu dùng khả năng tại một thời điểm từ \(0\) đến trước \(1\), cậu sẽ quay về thời điểm \(0\) của ngày đó. Bitaro chỉ có thể dùng khả năng khi đang ở một thành phố. Vị trí của cậu không thay đổi khi sử dụng khả năng.

Mỗi lần quay ngược thời gian đều khiến Bitaro mệt mỏi. Để tìm cách di chuyển mà sử dụng khả năng ít lần hơn, cậu thực hiện một thí nghiệm tưởng tượng gồm \(Q\) bước. Ở bước thứ \(j\), cậu thực hiện một trong hai việc:

Thay đổi khoảng thời gian có thể đi qua đường thứ \(P_j\). Sau thay đổi, đường này chỉ có thể được đi qua từ thời điểm \(S_j\) đến thời điểm \(E_j\).
Giả sử Bitaro đang ở thành phố \(A_j\) tại thời điểm \(B_j\). Tính số lần sử dụng khả năng ít nhất để cậu có mặt ở thành phố \(C_j\) tại thời điểm \(D_j\) trong cùng ngày.

Hãy tính kết quả của thí nghiệm này.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N Q
L_1 R_1
...
L_{N-1} R_{N-1}
Truy_van_1
...
Truy_van_Q

Mỗi truy vấn gồm bốn hoặc năm số nguyên, ngăn cách nhau bằng dấu cách. Gọi số đầu tiên là \(T_j\):

Nếu \(T_j=1\), truy vấn có dạng 1 P_j S_j E_j. Ở bước này, khoảng thời gian có thể đi qua đường thứ \(P_j\) được thay đổi thành khoảng từ \(S_j\) đến \(E_j\); tức là thời điểm khởi hành \(x\) phải thỏa mãn \(S_j \le x \le E_j-1\).
Nếu \(T_j=2\), truy vấn có dạng 2 A_j B_j C_j D_j. Hãy tính số lần sử dụng khả năng ít nhất để Bitaro có mặt ở thành phố \(C_j\) tại thời điểm \(D_j\) trong ngày đó, giả sử cậu bắt đầu ở thành phố \(A_j\) tại thời điểm \(B_j\).

Dữ liệu ra

Với mỗi truy vấn có \(T_j=2\), theo đúng thứ tự xuất hiện, ghi một dòng chứa số lần sử dụng khả năng ít nhất ra đầu ra chuẩn.

Ràng buộc

\(1 \le N \le 300\,000\).
\(1 \le Q \le 300\,000\).
\(0 \le L_i < R_i \le 999\,999\,999\) với \(1 \le i \le N-1\).
\(1 \le T_j \le 2\) với \(1 \le j \le Q\).
Với mọi truy vấn loại \(1\): \(1 \le P_j \le N-1\) và \(0 \le S_j < E_j \le 999\,999\,999\).
Với mọi truy vấn loại \(2\): \(1 \le A_j,C_j \le N\) và \(0 \le B_j,D_j \le 999\,999\,999\).

Phân nhóm

\(4\) điểm: \(N \le 1\,000\) và \(Q \le 1\,000\).
\(30\) điểm: \(T_j=2\) với mọi \(1 \le j \le Q\); không có truy vấn thay đổi đường.
\(66\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

2
4

Giải thích

Ở bước thứ nhất, Bitaro đi từ thành phố \(1\) đến thành phố \(2\) trong \(1\) Byou, rồi đi từ thành phố \(2\) đến thành phố \(3\) trong \(1\) Byou, đến thành phố \(3\) tại thời điểm \(5\). Sau đó, dùng khả năng hai lần sẽ đưa cậu về thời điểm \(3\) tại thành phố \(3\).

Ở bước thứ hai, khoảng thời gian có thể đi qua đường thứ \(2\) được thay đổi thành từ thời điểm \(0\) đến thời điểm \(1\).

Ở bước thứ ba, Bitaro đi từ thành phố \(1\) đến thành phố \(2\) trong \(1\) Byou, đến nơi tại thời điểm \(4\). Cậu dùng khả năng bốn lần, đi đến thành phố \(3\) trong \(1\) Byou, rồi chờ thêm \(2\) Byou để có mặt ở thành phố \(3\) tại thời điểm \(3\).

Ví dụ 2

Input

Output

Ví dụ 3

Input

7 7
112103440 659752416
86280800 902409187
104535475 965602300
198700180 945132880
137957976 501365807
257419446 565237610
2 4 646977260 7 915994878
2 1 221570340 6 606208433
2 7 948545948 4 604273995
2 7 247791098 5 944822313
2 7 250362511 2 50167280
2 3 364109400 4 555412865
2 7 33882587 7 186961394

Output

Ví dụ 4

Input

7 7
535825574 705426142
964175291 996597835
481817391 649559926
4519006 410772613
74521477 274584126
256535565 899389890
1 6 511428966 602601933
1 1 69986642 201421232
2 3 636443425 4 625975977
1 6 235225515 405336399
2 3 866680458 3 701821857
1 6 180606048 900533151
1 6 612564160 720179605

Output

10467449
164858601

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 3 (22/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.