JOI 2018 Final Camp - Ngày 1

Vương quốc JOI có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Thành phố \(1\) là thủ đô. Mỗi thành phố có một giá trị gọi là độ sầm uất; ban đầu, độ sầm uất của thành phố \(i\) là \(C_i\).

Mỗi con đường nối hai thành phố khác nhau và có thể đi theo cả hai chiều. Ban đầu chưa có con đường nào. Bạn dự định xây \(N-1\) con đường. Lần xây dựng thứ \(j\) được thực hiện như sau:

1. Chọn hai thành phố \(A_j\) và \(B_j\) sao cho, chỉ dùng những con đường đã xây, có thể đi từ thành phố \(1\) đến \(A_j\) nhưng không thể đi từ thành phố \(1\) đến \(B_j\).
2. Xây một con đường nối \(A_j\) với \(B_j\). Chi phí là số cặp thành phố \((s,t)\) thỏa mãn đồng thời: cả \(s\) và \(t\) nằm trên đường đi ngắn nhất từ \(1\) đến \(A_j\); khi đi từ \(1\) đến \(A_j\) thì gặp \(s\) trước \(t\); và độ sầm uất hiện tại của \(s\) lớn hơn hẳn độ sầm uất hiện tại của \(t\). Đường đi này là duy nhất và bao gồm cả hai đầu mút \(1\) và \(A_j\).
3. Đổi độ sầm uất của tất cả thành phố trên đường đi từ \(1\) đến \(A_j\) thành độ sầm uất của thành phố \(B_j\).

Hãy tính chi phí của từng lần xây dựng.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(C_1,C_2,\ldots,C_N\).
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(A_j,B_j\), mô tả lần xây dựng thứ \(j\).

Dữ liệu ra

In \(N-1\) dòng. Dòng thứ \(j\) chứa chi phí của lần xây dựng thứ \(j\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le A_j,B_j \le N\) với \(1 \le j \le N-1\).
• Trước lần xây dựng thứ \(j\), có thể đi từ thành phố \(1\) đến \(A_j\) nhưng không thể đi từ thành phố \(1\) đến \(B_j\) bằng các con đường đã xây.

Phân nhóm

1. \(7\) điểm: \(N \le 500\)
2. \(9\) điểm: \(N \le 4\,000\)
3. \(84\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

0
0
0
2

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

0
0
0
1
1
0
1
2
3

Nguồn

JOI 2018 Spring Training Camp, ngày 1 - Construction of Highway.

Ông JOI sở hữu một khu đất rộng ở đất nước IOI. Đất nước được biểu diễn bằng mặt phẳng tọa độ với hai trục \(X,Y\) vuông góc. Điểm có hoành độ \(x\) và tung độ \(y\) được ký hiệu là \((x,y)\). Khu đất của ông gồm các điểm có cả hoành độ lẫn tung độ nằm trong đoạn \([-10^{100},10^{100}]\). Trong khu đất, ông nuôi bò trên một đồng cỏ gồm các điểm có cả hoành độ lẫn tung độ nằm trong đoạn \([-S,S]\).

Ông muốn dùng hàng rào bao kín đồng cỏ để giữ bò. Mỗi hàng rào là một đoạn thẳng có độ dài là số thực dương. Việc bao kín phải bảo đảm không thể đi từ bất kỳ điểm nào bên trong đồng cỏ ra ngoài khu đất mà không đi qua một điểm thuộc hàng rào, kể cả đầu mút của hàng rào.

Trong khu đất đã có một số hàng rào mà ông có thể tận dụng. Nếu hai hàng rào có sẵn có điểm chung thì điểm đó là đầu mút của ít nhất một trong hai hàng rào.

Ông có thể xây thêm bao nhiêu hàng rào cũng được. Mỗi hàng rào mới có thể có độ dài và hướng tùy ý, nhưng không được đi qua phần bên trong đồng cỏ hoặc ra ngoài khu đất. Hàng rào có thể nằm dọc theo biên đồng cỏ. Xây hàng rào dài \(l>0\) tốn chi phí \(l\). Các hàng rào có thể cắt nhau; đầu mút của một hàng rào có thể trùng với đầu mút hoặc nằm trên một hàng rào khác.

Hãy tính tổng chi phí nhỏ nhất để bao kín đồng cỏ.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,S\): số hàng rào có sẵn và kích thước đồng cỏ.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(A_i,B_i,C_i,D_i\). Hàng rào có sẵn thứ \(i\) là đoạn thẳng nối \((A_i,B_i)\) và \((C_i,D_i)\).

Dữ liệu ra

In tổng chi phí nhỏ nhất trên một dòng. Có thể in tùy ý số chữ số sau dấu thập phân, nhưng sai số tuyệt đối so với đáp án đúng phải không vượt quá \(0.01\).

Ràng buộc

• \(1 \le N \le 100\).
• \(1 \le S \le 200\).
• \(-200 \le A_i,B_i,C_i,D_i \le 200\) với \(1 \le i \le N\).
• \((A_i,B_i) \ne (C_i,D_i)\) với \(1 \le i \le N\).
• Không hàng rào nào trong dữ liệu vào đi qua phần bên trong đồng cỏ.
• Nếu hai hàng rào khác nhau trong dữ liệu vào có điểm chung thì điểm đó là đầu mút của ít nhất một trong hai hàng rào.

Phân nhóm

1. \(18\) điểm: \(N=1\)
2. \(33\) điểm: \(N \le 6\)
3. \(49\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

29.0000000000

1 2
-3 -3 -3 -2

16.0000000000

4 3
4 -1 3 4
-4 2 -2 4
-4 0 -5 6
0 -6 5 -2

14.1392801789

10 80
175 95 60 -146
-106 57 18 185
190 -68 177 -142
84 -195 127 -179
34 143 126 69
-92 133 -190 80
-157 -66 -119 -161
-85 -124 129 -171
141 181 175 175
107 -38 150 148

238.4778364511

Nguồn

JOI 2018 Spring Training Camp, ngày 1 - Fences.

JOI-kun quản lý một khu cắm trại được chia thành lưới chữ nhật gồm \(H\) hàng và \(W\) cột. Các hàng chạy theo hướng đông-tây, các cột chạy theo hướng bắc-nam. Ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây được gọi là ô \((i,j)\).

JOI-kun muốn dựng một số lều. Mỗi lều chiếm đúng một ô, và không có hai lều chiếm cùng một ô. Mỗi lều có đúng một cửa ra vào, hướng về một trong bốn phía bắc, nam, đông hoặc tây. Hướng cửa phải thỏa mãn:

• Nếu cả hai ô \((i_1,j)\) và \((i_2,j)\), với \(1 \le i_1 < i_2 \le H\) và \(1 \le j \le W\), đều có lều, thì cửa lều ở \((i_1,j)\) phải hướng nam, còn cửa lều ở \((i_2,j)\) phải hướng bắc.
• Nếu cả hai ô \((i,j_1)\) và \((i,j_2)\), với \(1 \le i \le H\) và \(1 \le j_1 < j_2 \le W\), đều có lều, thì cửa lều ở \((i,j_1)\) phải hướng đông, còn cửa lều ở \((i,j_2)\) phải hướng tây.

Hãy đếm số cách dựng ít nhất một lều thỏa mãn các điều kiện trên, lấy dư cho \(1\,000\,000\,007\). Hai cách khác nhau nếu có một ô mà trạng thái khác nhau: có hay không có lều, hoặc hướng cửa lều khác nhau.

Dữ liệu vào

Một dòng chứa hai số nguyên \(H,W\).

Dữ liệu ra

In số cách dựng ít nhất một lều thỏa mãn điều kiện, lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le H \le 3\,000\).
• \(1 \le W \le 3\,000\).

Phân nhóm

1. \(48\) điểm: \(1 \le H \le 300\) và \(1 \le W \le 300\)
2. \(52\) điểm: Không có ràng buộc bổ sung.

Ví dụ

1 2

9

4 3

3252

100 100

561068619

Nguồn

JOI 2018 Spring Training Camp, ngày 1 - Tents (tiếng Anh). Bản tiếng Nhật.