Ở vương quốc IOI, đơn vị thời gian là Byou. Một ngày được chia thành \(S\) Byou. Thời điểm sau đầu ngày \(x\) Byou (\(0\le x<S\)) được gọi là thời điểm \(x\). Vương quốc có \(N\) thành phố, đánh số từ \(0\) đến \(N-1\), và \(M\) con đường, đánh số từ \(0\) đến \(M-1\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các con đường.

Con đường \(i\) (\(0\le i\le M-1\)) nối hai thành phố \(A_i,B_i\) theo cả hai chiều. Đi từ một đầu đến đầu kia mất \(L_i\) Byou. Mỗi ngày, con đường này bị kiểm tra an ninh nghiêm ngặt từ thời điểm \(C_i\) đến hết ngày.

Hội JOI là một tổ chức bí mật trong vương quốc. Danh tính thành viên phải được giữ kín, nên họ không được gặp các đợt kiểm tra. Để đi qua đường \(i\), một thành viên phải rời \(A_i\) hoặc \(B_i\) vào thời điểm \(x\) và đến đầu kia vào thời điểm \(x+L_i\), với \(0\le x\le C_i-L_i\). Không có kiểm tra trong các thành phố, nên thành viên có thể ở tại \(A_i\) hoặc \(B_i\) khi đường \(i\) đang bị kiểm tra.

Hội có \(Q\) thành viên, đánh số từ \(0\) đến \(Q-1\). Thành viên \(j\) rời thành phố \(U_j\) vào thời điểm \(T_j\) của một ngày nào đó để đi đến \(V_j\). Họ có thể chờ trong các thành phố trên đường đi. Hành trình có thể kéo dài qua nhiều ngày.

Cho thông tin thành phố, đường đi, các đợt kiểm tra và các thành viên, hãy tính thời gian ít nhất để mỗi thành viên \(j\) đi từ \(U_j\) đến \(V_j\).

Chi tiết cài đặt

Để tăng tốc nhập xuất, bài này sử dụng chương trình chấm (grader). Bạn cần nộp một tệp escape_route.cpp, nạp escape_route.h bằng chỉ thị #include, và cài đặt hàm:

std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q,
    std::vector<int> A, std::vector<int> B,
    std::vector<long long> L, std::vector<long long> C,
    std::vector<int> U, std::vector<int> V, std::vector<long long> T);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu.

• N, M, S, Q lần lượt là số thành phố, số con đường, số Byou trong một ngày và số thành viên.
• A, B, L, C là các mảng độ dài \(M\). Đường \(i\) nối A[i] với B[i], mất L[i] Byou để đi qua, và bắt đầu bị kiểm tra lúc C[i] mỗi ngày.
• U, V, T là các mảng độ dài \(Q\). Thành viên \(j\) rời U[j] lúc T[j] để đi đến V[j].
• Hàm phải trả về mảng answer kiểu long long, độ dài \(Q\). Với mỗi \(0\le j\le Q-1\), answer[j] là thời gian ít nhất, tính bằng Byou, để thành viên \(j\) đi từ U[j] đến V[j].

Lưu ý quan trọng

• Chương trình của bạn không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.
• Grader không kiểm tra định dạng đầu vào. Nếu định dạng sai, hoạt động của grader không được bảo đảm.
• Nếu mảng trả về có độ dài khác \(Q\) hoặc chứa số âm, hoạt động của grader không được bảo đảm.

Biên dịch và chạy thử

Trang cuộc thi cung cấp một gói gồm grader và tệp chương trình mẫu. Đặt grader.cpp, escape_route.cpp, escape_route.h trong cùng thư mục, rồi biên dịch bằng lệnh:

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp

Nếu thành công, tệp thực thi grader được tạo. Trong bài này, grader công khai trên trang cuộc thi giống grader thực tế dùng để chấm trên CMS.

Dữ liệu vào

Grader đọc từ đầu vào chuẩn theo định dạng sau; mọi giá trị đều là số nguyên:

N M S Q
A_0 B_0 L_0 C_0
...
A_{M-1} B_{M-1} L_{M-1} C_{M-1}
U_0 V_0 T_0
...
U_{Q-1} V_{Q-1} T_{Q-1}

Dữ liệu ra

Grader in \(Q\) dòng. Dòng thứ \(k+1\) (\(0\le k\le Q-1\)) chứa answer[k].

Ràng buộc

• \(2\le N\le90\).
• \(N-1\le M\le N(N-1)/2\).
• \(2\le S\le10^{15}\).
• \(1\le Q\le3000000\).
• \(0\le A_i,B_i\le N-1\) và \(A_i\ne B_i\) với mọi \(0\le i\le M-1\).
• Với \(0\le i<k\le M-1\), \((A_i,B_i)\ne(A_k,B_k)\) và \((A_i,B_i)\ne(B_k,A_k)\).
• \(1\le L_i<S\) và \(L_i\le C_i<S\) với mọi \(0\le i\le M-1\).
• Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các con đường.
• \(0\le U_j,V_j\le N-1\), \(U_j\ne V_j\) và \(0\le T_j<S\) với mọi \(0\le j\le Q-1\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le40\) và \(Q\le1000\).
• Nhóm 2 (20 điểm): \(N\le40\) và \(U_j=0\) với mọi \(0\le j\le Q-1\).
• Nhóm 3 (10 điểm): \(N\le40\).
• Nhóm 4 (35 điểm): \(N\le60\).
• Nhóm 5 (30 điểm): Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

Dữ liệu ra của trình chấm mẫu:

3
8
14
2
5
7

Giải thích

Thành viên \(0\) rời thành phố \(0\) lúc \(5\) để đến thành phố \(3\). Đi đường \(1\) từ thành phố \(0\) lúc \(5\) đến thành phố \(2\) lúc \(7\), rồi đi đường \(4\) lúc \(7\) đến thành phố \(3\) lúc \(8\). Đây là thời gian ít nhất, nên answer[0] = 3.

Thành viên \(1\) rời thành phố \(0\) lúc \(7\). Đi đường \(0\) lúc \(7\) đến thành phố \(1\) lúc \(10\); đi đường \(2\) lúc \(10\) đến thành phố \(2\) lúc \(14\); đi đường \(4\) lúc \(14\) đến thành phố \(3\) lúc \(15\). Đây là thời gian ít nhất, nên answer[1] = 8.

Thành viên \(2\) rời thành phố \(0\) lúc \(9\). Chờ ở thành phố \(0\) đến thời điểm \(0\) ngày hôm sau; đi đường \(1\) đến thành phố \(2\) lúc \(2\), rồi đi đường \(4\) đến thành phố \(3\) lúc \(3\). Tổng thời gian là \(14\) Byou và là ít nhất, nên answer[2] = 14.

Ví dụ này thỏa mãn các nhóm \(1,3,4,5\).

Ví dụ 2

Dữ liệu vào của trình chấm mẫu:

6 10 100 9
5 3 4 29
1 0 6 26
0 4 2 7
0 5 18 18
2 0 79 82
3 4 35 46
1 2 15 57
2 4 3 6
4 1 21 83
3 2 47 53
0 2 63
0 4 70
0 4 98
0 5 25
0 5 19
0 4 96
0 5 2
0 3 62
0 3 83

Dữ liệu ra của trình chấm mẫu:

42
32
4
93
99
6
102
60
39

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,2,3,4,5\).

Ví dụ 3

Dữ liệu vào của trình chấm mẫu:

8 12 1000000000000000 13
2 0 4451698272827 120985696255786
6 5 78520421713825 342652131468508
2 1 185377268405175 382583457603811
0 4 54350742205838 133614919589507
7 0 68486247989149 651590905094148
0 6 85177550834829 299184420663240
5 2 442329739732459 926608308293721
3 7 78020232822359 913548478810253
1 3 267796317244889 687571310475622
5 4 90590208828121 910324397566584
5 7 8414633059584 17796117322043
4 6 45682367792138 204548471584556
7 2 44779065000162
3 5 79376234836942
4 7 305556687070759
4 3 927935834343174
5 1 663284649258985
2 5 967584209777344
5 2 963749709374595
7 4 484562389171308
1 5 446160773830045
6 4 801452311055604
3 1 744524289545354
0 6 467418420721777
5 6 371181379240653

Dữ liệu ra của trình chấm mẫu:

72937946261976
929038398222642
702857945988825
272921388674172
580895059624855
181808439529442
117602869946965
569788353034530
1181546234307589
244230056736534
513790925121797
617759130113052
674500988551485

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,3,4,5\).

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 2. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.