| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2023 December Contest, Gold, Flight Routes | 100 (p) | 2.0s | 256M |
| 2 | USACO 2023 December Contest, Gold, Minimum Longest Trip | 100 (p) | 2.0s | 256M |
| 3 | USACO 2023 December Contest, Gold, Haybale Distribution | 100 (p) | 2.0s | 256M |
Bessie mới phát hiện rằng nghệ sĩ nhạc pop yêu thích của cô, Elsie Swift, đang biểu diễn trong chuyến lưu diễn "Eras Tour" mới của mình! Thật không may, vé đang bán rất nhanh, vì vậy Bessie đang nghĩ đến việc bay tới một thành phố khác để tham dự buổi hòa nhạc. Chuyến lưu diễn "Eras" đang diễn ra tại \(N\) \((2 \leq N \leq 750)\) thành phố được đánh số từ 1 đến \(N\), và đối với mỗi cặp thành phố \((i,j)\) với \(i < j\), có thể tồn tại một chuyến bay trực tiếp từ \(i\) đến \(j\) hoặc không.
Một tuyến bay từ thành phố \(a\) đến thành phố \(b\) \((a < b)\) là một dãy gồm \(k \ge 2\) thành phố \(a = c_1 < c_2 < \dots < c_k = b\) sao cho đối với mỗi \(1 \le i < k\), tồn tại một chuyến bay trực tiếp từ thành phố \(c_i\) đến thành phố \(c_{i+1}\).
Đối với mỗi cặp thành phố \((i,j)\) với \(i < j\), bạn được cung cấp độ chẵn/lẻ (parity) của số lượng tuyến bay giữa chúng (0 là chẵn, 1 là lẻ).
Trong khi lên kế hoạch cho chuyến đi, Bessie bị phân tâm và bây giờ muốn biết có bao nhiêu cặp thành phố có chuyến bay trực tiếp giữa chúng. Có thể chứng minh rằng đáp án là duy nhất.
Test 1
3
1 1
12Test 2
5
1 1 1 1
1 0 1
0 1
16| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 | 3 |
| 2 | 0 | 1 | 0 | 1 | |
| 3 | 0 | 0 | 1 | ||
| 4 | 0 | 1 | |||
| 5 | 0 |
Bessie đang đi du lịch ở Cowland, nơi có \(N\) \((2 \leq N \leq 2 \cdot 10^5)\) thị trấn, được đánh số từ 1 đến \(N\), và \(M\) \((1 \leq M \leq 4 \times 10^5)\) con đường một chiều. Con đường thứ \(i\) chạy từ thị trấn \(a_i\) đến thị trấn \(b_i\) và có nhãn \(l_i\) \((1 \leq a_i, b_i \leq N; 1 \leq l_i \leq 10^9)\).
Một chuyến đi có độ dài \(k\) bắt đầu tại thị trấn \(x_0\) là một dãy các thị trấn \(x_0, x_1, \dots, x_k\), sao cho có một con đường từ thị trấn \(x_i\) đến thị trấn \(x_{i+1}\) đối với mọi \(0 \leq i < k\). Đảm bảo rằng không có chuyến đi nào có độ dài vô hạn trong Cowland và không có hai con đường nào kết nối cùng một cặp thị trấn.
Với mỗi thị trấn, Bessie muốn biết chuyến đi dài nhất có thể bắt đầu từ đó. Đối với một số thị trấn xuất phát, có nhiều chuyến đi dài nhất. Nếu có nhiều chuyến đi dài nhất, Bessie ưu tiên chuyến đi có thứ tự nhãn của các con đường có thứ tự từ điển nhỏ nhất. Một dãy được coi là có thứ tự từ điển nhỏ hơn so với một dãy khác cùng độ dài nếu tại vị trí đầu tiên mà chúng khác nhau, phần tử của dãy đó nhỏ hơn phần tử của dãy còn lại.
Test 1
4 5
4 3 10
4 2 10
3 1 10
2 1 10
4 1 100 0
1 10
1 10
2 20Test 2
4 5
4 3 4
4 2 2
3 1 5
2 1 10
4 1 10 0
1 10
1 5
2 12Test 3
4 5
4 3 2
4 2 2
3 1 5
2 1 10
4 1 10 0
1 10
1 5
2 7Test 4
4 5
4 3 2
4 2 2
3 1 10
2 1 5
4 1 10 0
1 5
1 10
2 7nh nông dân John đang phân phối các kiện cỏ khô khắp trang trại!
Trang trại của John có \(N\) \((1 \leq N \leq 2 \times 10^5)\) kho chứa, nằm tại các điểm nguyên \(x_1, \dots, x_N\) \((0 \leq x_i \leq 10^6)\) trên trục số. Kế hoạch của John là nhận \(N\) chuyến hàng kiện cỏ khô được chuyển đến một số điểm nguyên \(y\) \((0 \leq y \leq 10^6)\), sau đó phân phối một chuyến hàng đến mỗi kho chứa.
Không may, dịch vụ phân phối của John lại rất lãng phí. Cụ thể, đối với một số \(a_i\) và \(b_i\) \((1 \leq a_i, b_i \leq 10^6)\), mỗi kiện cỏ bị lãng phí \(a_i\) kiện trên mỗi đơn vị khoảng cách nếu vận chuyển sang trái, và bị lãng phí \(b_i\) kiện trên mỗi đơn vị khoảng cách nếu vận chuyển sang phải. Cụ thể, đối với một kiện hàng được vận chuyển từ điểm \(y\) đến một kho chứa tại điểm \(x\), số kiện cỏ bị lãng phí được tính theo công thức:
Yêu cầu: Với mỗi \(Q\) truy vấn \((1 \leq Q \leq 2 \times 10^5)\), mỗi truy vấn bao gồm các giá trị \((a_i, b_i)\), hãy giúp John tính toán số lượng kiện cỏ bị lãng phí ít nhất có thể nếu anh ta chọn \(y\) một cách tối ưu.
Test 1
5
1 4 2 3 10
4
1 1
2 1
1 2
1 411
13
18
30