IOI 2023 - Ngày 1

Hungary là đất nước có \(N\) thành phố, đánh số từ \(0\) đến \(N-1\).

Các thành phố được nối với nhau bằng \(N-1\) con đường hai chiều, được đánh số từ \(0\) đến \(N-2\). Với mỗi \(j\) mà \(0 \le j \le N-2\), con đường \(j\) nối thành phố \(U[j]\) với thành phố \(V[j]\) và có độ dài \(W[j]\), nghĩa là một người đi giữa hai thành phố mất \(W[j]\) đơn vị thời gian. Mỗi con đường nối hai thành phố phân biệt và mỗi cặp thành phố được nối bởi nhiều nhất một con đường.

Một đường đi giữa hai thành phố phân biệt \(a\) và \(b\) là một chuỗi \(p_0,p_1,\ldots,p_t\) các thành phố khác nhau, sao cho:

• \(p_0=a\);
• \(p_t=b\);
• với mỗi \(i\) (\(0 \le i < t\)), có một con đường nối thành phố \(p_i\) và \(p_{i+1}\).

Có thể đi lại từ một thành phố bất kì đến một thành phố bất kì khác sử dụng các con đường, nghĩa là có một đường đi giữa hai thành phố phân biệt bất kì. Có thể chứng minh rằng đường đi này là duy nhất cho từng cặp thành phố phân biệt.

Độ dài của một đường đi \(p_0,p_1,\ldots,p_t\) là tổng độ dài của \(t\) con đường nối các thành phố liên tiếp nhau dọc theo đường đi đó.

Ở Hungary, nhiều người di chuyển để tham gia các lễ hội ngày Quốc khánh tại hai thành phố lớn. Khi các buổi ăn mừng kết thúc, họ quay trở về nhà. Chính quyền muốn tránh việc các đám đông làm phiền cư dân địa phương, nên dự định ra lệnh giới nghiêm ở tất cả các thành phố vào các thời điểm nhất định. Chính quyền gán cho mỗi thành phố một thời điểm đóng cửa không âm và quyết định rằng tổng các thời điểm đóng cửa không vượt quá \(K\). Cụ thể, với mỗi \(i\) từ \(0\) đến \(N-1\), thời điểm đóng cửa được gán cho thành phố \(i\) là số nguyên không âm \(c[i]\). Tổng của tất cả các số \(c[i]\) không vượt quá \(K\).

Xét thành phố \(a\) và một cách gán thời điểm đóng cửa. Ta nói thành phố \(b\) đến được từ thành phố \(a\) khi và chỉ khi hoặc \(b=a\), hoặc đường đi \(p_0,\ldots,p_t\) giữa hai thành phố này (nghĩa là \(p_0=a\) và \(p_t=b\)) thỏa mãn các điều kiện sau:

• độ dài đường đi \(p_0,p_1\) không vượt quá \(c[p_1]\), và
• độ dài đường đi \(p_0,p_1,p_2\) không vượt quá \(c[p_2]\), và
• \(\ldots\)
• độ dài đường đi \(p_0,p_1,p_2,\ldots,p_t\) không vượt quá \(c[p_t]\).

Trong năm nay, hai địa điểm chính tổ chức lễ hội đặt tại thành phố \(X\) và thành phố \(Y\). Với mỗi cách gán thời điểm đóng cửa, điểm thuận tiện được định nghĩa là tổng của hai số sau:

• Số lượng thành phố đến được từ thành phố \(X\).
• Số lượng thành phố đến được từ thành phố \(Y\).

Lưu ý rằng nếu một thành phố đến được từ thành phố \(X\) và cũng đến được từ thành phố \(Y\) thì thành phố đó được tính hai lần vào điểm thuận tiện.

Nhiệm vụ của bạn là tính điểm thuận tiện lớn nhất có thể đạt được bởi một cách gán thời điểm đóng cửa.

Chi tiết cài đặt

Bạn phải cài đặt hàm sau:

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W);

• \(N\): số lượng thành phố.
• \(X,Y\): hai thành phố có địa điểm chính tổ chức lễ hội.
• \(K\): cận trên của tổng thời điểm đóng cửa.
• \(U,V\): các mảng có kích thước \(N-1\) mô tả hai đầu của các con đường.
• \(W\): mảng có kích thước \(N-1\) mô tả độ dài các con đường.
• Hàm này phải trả về điểm thuận tiện lớn nhất có thể đạt được bởi một cách gán thời điểm đóng cửa.
• Hàm này có thể được gọi nhiều lần trong mỗi test.

Ví dụ

Xét lời gọi hàm sau:

max_score(7, 0, 2, 10,
          [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3])

Lời gọi này tương ứng với mạng lưới các con đường sau:

Giả sử các thời điểm đóng cửa được gán như sau:

Lưu ý rằng tổng thời điểm đóng cửa là \(9\), không vượt quá \(K=10\). Các thành phố \(0,1,3\) đến được từ thành phố \(X\) (\(X=0\)), trong khi các thành phố \(1,2,4\) đến được từ thành phố \(Y\) (\(Y=2\)). Vì thế, điểm thuận tiện là \(3+3=6\). Không có cách gán thời điểm đóng cửa nào có điểm thuận tiện lớn hơn \(6\), do đó hàm phải trả về \(6\).

Xét lời gọi hàm sau:

max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19])

Lời gọi này tương ứng với mạng lưới các con đường sau:

Giả sử các thời điểm đóng cửa được gán như sau:

Thành phố \(0\) đến được từ thành phố \(X\) (\(X=0\)), trong khi các thành phố \(2,3\) đến được từ thành phố \(Y\) (\(Y=3\)). Vì thế, điểm thuận tiện là \(1+2=3\). Không có cách gán thời điểm đóng cửa nào có điểm thuận tiện lớn hơn \(3\), do đó hàm phải trả về \(3\).

Các ràng buộc

• \(2 \le N \le 200\,000\).
• \(0 \le X < Y < N\).
• \(0 \le K \le 10^{18}\).
• \(0 \le U[j] < V[j] < N\) (với mỗi \(j\) mà \(0 \le j \le N-2\)).
• \(1 \le W[j] \le 10^6\) (với mỗi \(j\) mà \(0 \le j \le N-2\)).
• Có thể đi từ thành phố bất kì đến một thành phố bất kì khác sử dụng các con đường.
• \(S_N \le 200\,000\), với \(S_N\) là tổng các giá trị \(N\) trong tất cả lời gọi đến max_score trong mỗi test.

Các subtask

Ta nói một mạng lưới các con đường là đường thẳng nếu con đường \(i\) nối thành phố \(i\) và \(i+1\) (với mỗi \(i\) mà \(0 \le i \le N-2\)).

Trình chấm mẫu

Đặt \(C\) là số lượng kịch bản, tức là số lần gọi đến max_score. Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: C

Theo sau là mô tả của \(C\) kịch bản. Trình chấm mẫu đọc mô tả của từng kịch bản theo định dạng sau:

dòng 1: N X Y K
dòng 2 + j (0 ≤ j ≤ N − 2): U[j] V[j] W[j]

Trình chấm mẫu in một dòng duy nhất cho từng kịch bản theo định dạng sau:

dòng 1: giá trị trả về của max_score

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.

Các nhà tổ chức IOI 2023 đang gặp khó khăn lớn! Họ đã quên lên kế hoạch chuyến đi đến Ópusztaszer cho ngày mai. Nhưng có lẽ chưa quá muộn...

Ở Ópusztaszer có \(N\) điểm du lịch được đánh số từ \(0\) đến \(N-1\). Một số cặp điểm này được nối bởi các con đường hai chiều. Mỗi cặp điểm du lịch được nối bởi tối đa một con đường. Các nhà tổ chức không biết những điểm nào được nối bởi các con đường.

Chúng ta nói rằng mật độ của mạng lưới đường đi ở Ópusztaszer tối thiểu là \(\delta\) nếu mỗi bộ \(3\) điểm du lịch khác nhau có ít nhất \(\delta\) con đường giữa chúng. Nói cách khác, đối với mỗi bộ ba điểm \((u,v,w)\) sao cho \(0 \le u < v < w < N\), trong số các cặp điểm \((u,v)\), \((v,w)\) và \((u,w)\) có ít nhất \(\delta\) cặp được nối bởi một con đường.

Các nhà tổ chức biết một số nguyên dương \(D\) sao cho mật độ của mạng lưới đường đi tối thiểu là \(D\). Lưu ý rằng giá trị của \(D\) không thể lớn hơn \(3\).

Các nhà tổ chức có thể gọi điện tới bộ phận điều phối ở Ópusztaszer để thu thập thông tin về các kết nối đường đi giữa một số điểm du lịch. Trong mỗi cuộc gọi, họ cần xác định hai mảng không rỗng của các điểm du lịch \([A[0],\ldots,A[P-1]]\) và \([B[0],\ldots,B[R-1]]\). Các điểm du lịch phải đôi một khác nhau, nghĩa là:

• \(A[i] \ne A[j]\) với mọi \(i,j\) sao cho \(0 \le i < j < P\);
• \(B[i] \ne B[j]\) với mọi \(i,j\) sao cho \(0 \le i < j < R\);
• \(A[i] \ne B[j]\) với mọi \(i,j\) sao cho \(0 \le i < P\) và \(0 \le j < R\).

Đối với mỗi cuộc gọi, bộ phận điều phối báo cáo xem có con đường nối giữa một điểm du lịch từ \(A\) và một điểm du lịch từ \(B\) hay không. Cụ thể, bộ phận điều phối xét tất cả các cặp \(i,j\) sao cho \(0 \le i < P\) và \(0 \le j < R\). Nếu với bất kì cặp nào trong chúng, các điểm du lịch \(A[i]\) và \(B[j]\) được nối bởi một con đường, bộ phận điều phối trả về true. Nếu không, bộ phận điều phối trả về false.

Một hành trình có độ dài \(l\) là một chuỗi các điểm du lịch khác nhau \(t[0],t[1],\ldots,t[l-1]\), trong đó với mỗi \(i\) từ \(0\) đến \(l-2\) (kể cả hai đầu), điểm \(t[i]\) và điểm \(t[i+1]\) được nối bởi một con đường. Một hành trình có độ dài \(l\) được gọi là một hành trình dài nhất nếu không tồn tại bất kì hành trình nào có độ dài tối thiểu là \(l+1\).

Nhiệm vụ của bạn là giúp các nhà tổ chức tìm một hành trình dài nhất ở Ópusztaszer bằng cách thực hiện các cuộc gọi tới bộ phận điều phối.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> longest_trip(int N, int D);

• \(N\): số lượng điểm du lịch ở Ópusztaszer.
• \(D\): mật độ tối thiểu được đảm bảo của mạng lưới đường đi.
• Hàm này cần trả về một mảng \(t=[t[0],t[1],\ldots,t[l-1]]\), biểu diễn một hành trình dài nhất.
• Hàm này có thể được gọi nhiều lần trong mỗi test.

Hàm trên có thể gọi đến hàm sau:

bool are_connected(std::vector<int> A, std::vector<int> B);

• \(A\): một mảng không rỗng gồm các điểm du lịch khác nhau.
• \(B\): một mảng không rỗng gồm các điểm du lịch khác nhau.
• \(A\) và \(B\) phải không có phần tử chung.
• Hàm này trả về true nếu có một điểm du lịch từ \(A\) và một điểm du lịch từ \(B\) được nối bởi một con đường. Ngược lại, hàm trả về false.
• Hàm này có thể được gọi tối đa \(32\,640\) lần trong mỗi lời gọi longest_trip, và tối đa \(150\,000\) lần tổng cộng.
• Tổng độ dài của các mảng \(A\) và \(B\) được truyền vào hàm này qua tất cả các lần gọi không được vượt quá \(1\,500\,000\).

Trình chấm không thích nghi. Mỗi bài nộp được chấm trên cùng một bộ test. Nghĩa là các giá trị \(N\) và \(D\), cũng như các cặp điểm du lịch được nối bởi các con đường, đều cố định đối với mỗi lời gọi longest_trip trong mỗi test.

Các ví dụ

Ví dụ 1

Xét kịch bản khi \(N=5\), \(D=1\), và các kết nối đường đi được chỉ ra trong hình vẽ sau:

Hàm longest_trip được gọi theo cách sau:

longest_trip(5, 1)

Hàm này có thể thực hiện các lời gọi đến hàm are_connected như sau:

Sau lần gọi thứ tư, nhận thấy không có cặp nào trong số \((1,4)\), \((0,4)\), \((1,3)\) và \((0,3)\) được nối bởi một con đường. Vì mật độ của mạng ít nhất là \(D=1\), ta thấy rằng từ bộ ba \((0,3,4)\), cặp \((3,4)\) phải được nối bởi một con đường. Tương tự, các điểm du lịch \(0\) và \(1\) phải được nối với nhau.

Tại thời điểm này, có thể kết luận rằng \(t=[1,0,2,3,4]\) là một hành trình có độ dài \(5\) và không tồn tại hành trình có độ dài lớn hơn \(5\). Do đó, hàm longest_trip có thể trả về \([1,0,2,3,4]\).

Xét một kịch bản khác khi \(N=4\), \(D=1\), và các con đường giữa các điểm du lịch được chỉ ra trong hình sau:

Hàm longest_trip được gọi theo cách sau:

longest_trip(4, 1)

Trong kịch bản này, độ dài của hành trình dài nhất là \(2\). Do đó, sau một vài lời gọi đến hàm are_connected, hàm longest_trip có thể trả về một trong số \([0,1]\), \([1,0]\), \([2,3]\) hoặc \([3,2]\).

Ví dụ 2

Subtask \(0\) chứa thêm một test ví dụ với \(N=256\) điểm du lịch. Test này có trong gói đính kèm mà bạn có thể tải về từ hệ thống cuộc thi.

Các ràng buộc

• \(3 \le N \le 256\).
• Tổng các giá trị \(N\) trong tất cả lời gọi đến longest_trip không vượt quá \(1\,024\) trong mỗi test.
• \(1 \le D \le 3\).

Các subtask

Trong subtask \(4\), điểm của bạn được xác định dựa trên số lần gọi hàm are_connected trong một lần gọi longest_trip. Gọi \(q\) là số lần gọi lớn nhất trong số tất cả các lần gọi longest_trip trong mọi test của subtask. Điểm của bạn cho subtask này được tính theo bảng sau:

Nếu trong bất kì test nào các lời gọi hàm are_connected không tuân theo các ràng buộc được mô tả trong phần Chi tiết cài đặt, hoặc mảng được trả về bởi longest_trip không đúng, điểm cho lời giải của bạn đối với subtask đó sẽ là \(0\).

Trình chấm mẫu

Gọi \(C\) là số lượng kịch bản, nghĩa là số lần gọi đến longest_trip. Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: C

Theo sau là mô tả của \(C\) kịch bản. Trình chấm mẫu đọc mô tả mỗi kịch bản theo định dạng sau:

dòng 1: N D
dòng 1 + i (1 ≤ i < N): U_i[0] U_i[1] … U_i[i − 1]

Ở đây, mỗi \(U_i\) (\(1 \le i < N\)) là một mảng kích thước \(i\), mô tả các cặp điểm du lịch được nối bởi một con đường. Với mỗi \(i,j\) sao cho \(1 \le i < N\) và \(0 \le j < i\):

• nếu các điểm du lịch \(j\) và \(i\) được nối bởi một con đường thì \(U_i[j]\) phải bằng \(1\);
• nếu không có con đường nào nối các điểm du lịch \(j\) và \(i\) thì \(U_i[j]\) phải bằng \(0\).

Trong mỗi kịch bản, trước khi gọi longest_trip, trình chấm mẫu kiểm tra xem mật độ của mạng lưới đường đi có ít nhất là \(D\) hay không. Nếu điều kiện này không thỏa mãn, nó in thông báo Insufficient Density và kết thúc.

Nếu trình chấm mẫu phát hiện vi phạm giao thức, đầu ra của trình chấm mẫu là Protocol Violation: <MSG>, trong đó <MSG> là một trong các thông báo lỗi sau:

• invalid array: trong một lời gọi tới are_connected, ít nhất một trong hai mảng \(A\) và \(B\) là rỗng, hoặc chứa một phần tử không phải là số nguyên từ \(0\) đến \(N-1\) (kể cả hai đầu), hoặc có một phần tử xuất hiện ít nhất hai lần.
• non-disjoint arrays: trong một lời gọi tới are_connected, các mảng \(A\) và \(B\) có phần tử chung.
• too many calls: số lần gọi đến are_connected vượt quá \(32\,640\) trong lời gọi hiện tại tới longest_trip, hoặc vượt quá \(150\,000\) tổng cộng.
• too many elements: tổng số điểm du lịch được truyền vào are_connected trên tất cả các lời gọi vượt quá \(1\,500\,000\).

Ngược lại, gọi các phần tử của mảng được trả về bởi longest_trip trong một kịch bản là \(t[0],t[1],\ldots,t[l-1]\) với một số \(l\) không âm. Trình chấm mẫu in ba dòng đối với kịch bản này theo định dạng sau:

dòng 1: l
dòng 2: t[0] t[1] … t[l − 1]
dòng 3: số lần gọi tới are_connected trong kịch bản này

Cuối cùng, trình chấm mẫu in:

dòng 1 + 3 · C: số lần gọi tới are_connected lớn nhất trong tất cả các lần gọi tới longest_trip

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.

Nagyerdő là một khu rừng hình vuông nằm ở thành phố Debrecen, được mô hình hóa bằng một lưới ô vuông kích thước \(N \times N\). Các hàng của lưới được đánh số từ \(0\) đến \(N-1\) từ bắc xuống nam, và các cột được đánh số từ \(0\) đến \(N-1\) từ tây sang đông. Gọi ô nằm ở hàng \(r\) và cột \(c\) của lưới là ô \((r,c)\).

Trong khu rừng, mỗi ô hoặc trống hoặc chứa một cây. Có ít nhất một ô trống trong khu rừng.

DVSC, câu lạc bộ thể thao nổi tiếng của thành phố, đang có kế hoạch xây dựng một sân vận động bóng đá mới trong khu rừng. Một sân vận động có kích thước \(s\) (với \(s \ge 1\)) là một tập gồm \(s\) ô trống khác nhau \((r_0,c_0),\ldots,(r_{s-1},c_{s-1})\). Một cách chính xác:

• với mỗi \(i\) từ \(0\) đến \(s-1\) (kể cả hai đầu), ô \((r_i,c_i)\) là trống;
• với mỗi \(i,j\) mà \(0 \le i < j < s\), ít nhất một trong hai điều kiện \(r_i \ne r_j\) và \(c_i \ne c_j\) thỏa mãn.

Bóng đá được chơi bằng cách sử dụng một quả bóng di chuyển qua các ô của sân vận động. Một cú sút thẳng được định nghĩa là một trong hai hành động sau:

• Di chuyển quả bóng từ ô \((r,a)\) đến ô \((r,b)\) (\(0 \le r,a,b < N\), \(a \ne b\)), trong đó sân vận động chứa tất cả các ô giữa hai ô \((r,a)\) và \((r,b)\) trong hàng \(r\). Một cách chính xác:
• nếu \(a < b\) thì sân vận động phải chứa ô \((r,k)\) với mỗi \(k\) thỏa mãn \(a \le k \le b\);
• nếu \(a > b\) thì sân vận động phải chứa ô \((r,k)\) với mỗi \(k\) thỏa mãn \(b \le k \le a\).
• Di chuyển quả bóng từ ô \((a,c)\) đến ô \((b,c)\) (\(0 \le c,a,b < N\), \(a \ne b\)), trong đó sân vận động chứa tất cả các ô giữa hai ô \((a,c)\) và \((b,c)\) trong cột \(c\). Một cách chính xác:
• nếu \(a < b\) thì sân vận động phải chứa ô \((k,c)\) với mỗi \(k\) thỏa mãn \(a \le k \le b\);
• nếu \(a > b\) thì sân vận động phải chứa ô \((k,c)\) với mỗi \(k\) thỏa mãn \(b \le k \le a\).

Một sân vận động là chuẩn nếu có thể di chuyển quả bóng từ ô bất kì trong sân vận động đến bất kì ô nào khác trong sân vận động với tối đa \(2\) cú sút thẳng. Lưu ý rằng bất kì sân vận động nào có kích thước \(1\) đều là sân vận động chuẩn.

Ví dụ, xét một khu rừng có kích thước \(N=5\), với các ô \((1,0)\) và \((4,2)\) chứa cây và mọi ô khác đều trống. Hình dưới đây mô tả ba sân vận động có thể có. Các ô chứa cây được tô tối, các ô thuộc sân vận động có sọc.

Sân vận động bên trái là chuẩn. Tuy nhiên, sân vận động ở giữa không chuẩn, vì cần ít nhất \(3\) cú sút thẳng để di chuyển quả bóng từ ô \((4,1)\) đến \((4,3)\). Sân vận động bên phải cũng không chuẩn, vì không thể di chuyển quả bóng từ ô \((3,0)\) đến \((1,3)\) bằng các cú sút thẳng.

Câu lạc bộ thể thao muốn xây dựng một sân vận động chuẩn càng lớn càng tốt. Nhiệm vụ của bạn là tìm giá trị lớn nhất của \(s\) sao cho tồn tại một sân vận động chuẩn có kích thước \(s\) trong khu rừng.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int biggest_stadium(int N, std::vector<std::vector<int>> F);

• \(N\): kích thước khu rừng.
• \(F\): một mảng kích thước \(N\) mà mỗi phần tử là một mảng kích thước \(N\), mô tả các ô trong khu rừng. Với mỗi \(r,c\) thỏa mãn \(0 \le r < N\) và \(0 \le c < N\), \(F[r][c]=0\) nghĩa là ô \((r,c)\) trống, và \(F[r][c]=1\) nghĩa là ô chứa cây.
• Hàm cần trả về kích thước lớn nhất của sân vận động chuẩn có thể xây dựng trong khu rừng.
• Hàm được gọi đúng một lần với mỗi test.

Ví dụ

Xét lời gọi hàm sau:

biggest_stadium(5, [[0, 0, 0, 0, 0],
                    [1, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0],
                    [0, 0, 1, 0, 0]])

Trong ví dụ này, khu rừng được mô tả ở bên trái và một sân vận động chuẩn với kích thước \(20\) được mô tả ở bên phải của hình dưới đây:

Do không có sân vận động chuẩn nào có kích thước \(21\) hoặc lớn hơn nên hàm cần trả về \(20\).

Các ràng buộc

• \(1 \le N \le 2\,000\).
• \(0 \le F[i][j] \le 1\) (với mỗi \(i,j\) sao cho \(0 \le i < N\) và \(0 \le j < N\)).
• Có ít nhất một ô trống trong khu rừng. Nói cách khác, \(F[i][j]=0\) với một cặp \(i,j\) nào đó thỏa mãn \(0 \le i < N\) và \(0 \le j < N\).

Các subtask

Trong mỗi subtask, bạn có thể đạt được \(25\%\) số điểm của subtask nếu chương trình của bạn xác định chính xác liệu tập gồm tất cả các ô trống có phải là một sân vận động chuẩn hay không.

Chính xác hơn, đối với mỗi test trong đó tập gồm tất cả các ô trống là một sân vận động chuẩn, lời giải của bạn:

• nhận được điểm tối đa nếu trả về câu trả lời đúng (là kích thước của tập gồm tất cả các ô trống);
• nhận được \(0\) điểm trong các trường hợp còn lại.

Đối với mỗi test trong đó tập gồm tất cả các ô trống không phải là một sân vận động chuẩn, lời giải của bạn:

• nhận được điểm tối đa nếu trả về câu trả lời đúng;
• nhận được \(0\) điểm nếu trả về kích thước của tập gồm tất cả các ô trống;
• nhận được \(25\%\) số điểm nếu trả về bất kì giá trị nào khác.

Điểm cho mỗi subtask là điểm thấp nhất trong các test của subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: N
dòng 2 + i (0 ≤ i < N): F[i][0] F[i][1] … F[i][N − 1]

Trình chấm mẫu ghi kết quả của bạn theo định dạng sau:

dòng 1: giá trị trả về của biggest_stadium

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.