CEOI 2026 - Ngày 1

Hội những người quan sát chim có \(n\) chi hội. Chi hội \(i\) có \(m_i\) thành viên và có một trưởng chi hội, cũng được gọi là viên chức \(i\). Trừ đúng một Chủ tịch, mỗi viên chức có đúng một người cố vấn; không viên chức nào là cố vấn trực tiếp hay gián tiếp của chính mình, nên quan hệ cố vấn tạo thành một cây có gốc là Chủ tịch.

Ảnh hưởng của một viên chức là tổng số thành viên của chi hội của họ và ảnh hưởng của tất cả các đệ tử trực tiếp. Tổng ảnh hưởng của Chủ tịch là \(M=\sum_i m_i\). Một viên chức là cấp cao nếu ảnh hưởng của họ ít nhất \(M/2\). Thủ quỹ là viên chức cấp cao có ảnh hưởng nhỏ nhất.

Sau trạng thái ban đầu, có \(q\) lần thay đổi người cố vấn. Hãy in Thủ quỹ ở trạng thái ban đầu và sau mỗi thay đổi.

Dữ liệu vào

Dòng đầu chứa \(n,q\). Mỗi trong \(n\) dòng tiếp theo chứa \(s_i,m_i\): \(s_i\) là người cố vấn của viên chức \(i\), và \(s_i=0\) khi \(i\) là Chủ tịch. Mỗi trong \(q\) dòng cuối chứa \(\hat{x}_j,\hat{z}_j\). Nếu \(t_{j-1}\) là Thủ quỹ trước thay đổi \(j\), đặt

Thay đổi \(j\) khiến \(z_j\) trở thành cố vấn mới của \(x_j\). Mọi thay đổi đã được bảo đảm hợp lệ: \(z_j\ne x_j\) và \(z_j\) không phải đệ tử trực tiếp hay gián tiếp của \(x_j\). Vẫn có thể xảy ra \(z_j\) vốn đã là cố vấn của \(x_j\).

Dữ liệu ra

In \(t_0,t_1,\ldots,t_q\), mỗi số trên một dòng.

Ràng buộc

• \(1\le n\le1\,000\,000\), \(1\le q\le30\,000\).
• \(1\le m_i\) và \(\sum_i m_i\le10^9\).
• \(1\le\hat{x}_j,\hat{z}_j\le n\).

Nếu tính sai một \(t_j\), các thay đổi kế tiếp có thể bị giải mã sai; điều này có thể dẫn tới RTE thay vì WA.

Phân nhóm

1. \(15\) điểm: \(n\le100\).
2. \(10\) điểm: \(n\le1000\).
3. \(50\) điểm: \(n\le300\,000\).
4. \(25\) điểm: không có ràng buộc thêm.

Ví dụ

7 2
0 1
1 3
1 3
2 3
2 1
5 2
5 1
3 7
2 7

2
2
3

Nguồn

CEOI 2026 - Ngày 1, bài Birdwatchers.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.

Xét các đồ thị vô hướng đơn, liên thông, có các đỉnh \(0,1,\ldots,n-1\). Hàm DFS(d,v) in d/v, đánh dấu \(v\), rồi duyệt các đỉnh kề của \(v\) theo thứ tự tăng dần; với mỗi đỉnh chưa thăm \(w\), nó gọi DFS(d+1,w).

Bạn nhận được toàn bộ kết quả in của lời gọi DFS(0,n-1) trên một đồ thị chưa biết. Hãy đếm số đồ thị khác nhau có thể tạo ra đúng kết quả đó.

Dữ liệu vào

Gồm \(n\) dòng là kết quả của DFS, mỗi dòng có dạng d/v. Dòng đầu luôn là 0/n-1.

Dữ liệu ra

In số đồ thị thỏa mãn, lấy modulo \(1\,000\,000\,007\).

Ràng buộc

• \(1\le n\le2\cdot10^5\).

Phân nhóm

1. \(10\) điểm: \(n\le6\).
2. \(20\) điểm: \(n\le500\).
3. \(20\) điểm: \(n\le10^4\).
4. \(10\) điểm: với mọi \(i=2,\ldots,n\), dòng \(i\) là i-1/i-2.
5. \(20\) điểm: với mọi \(i=2,\ldots,n\), dòng \(i\) là i-1/v với \(v\in\{0,\ldots,n-2\}\).
6. \(20\) điểm: không có ràng buộc thêm.

Ví dụ

0/2
1/0
2/1

2

Nguồn

CEOI 2026 - Ngày 1, bài DFS.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.

Trên bàn cờ \(N\times N\) có \(K\le3\) kho báu ở các ô khác nhau. Khi hỏi một ô, la bàn trả về hướng của mọi bước đầu tiên nằm trên một đường Manhattan ngắn nhất tới một kho báu gần nhất. Nếu ô có kho báu, nó trả về TREASURE. Kho báu đã tìm vẫn tồn tại và vẫn ảnh hưởng tới la bàn. Tọa độ \(y\) tăng từ trên xuống dưới.

Đây là bài tương tác. Submission C++ của bạn có một hàm main và phải dùng thư viện treasurehuntlib.h; không được đọc standard input hay ghi standard output. Chỉ được ghi thông tin gỡ lỗi vào standard error.

Giao diện thư viện

Bạn không cài đặt NextHunt hay Query. Submission cần cài đặt hàm main, include treasurehuntlib.h và gọi hai hàm do bộ chấm cung cấp.

Header cung cấp chính xác giao diện sau:

enum {
    TREASURE = 0,
    DIR_RIGHT = 1,
    DIR_UP = 2,
    DIR_LEFT = 4,
    DIR_DOWN = 8,
};

void NextHunt(int &N, int &K);
int Query(int x, int y);

Khung chương trình tối thiểu:

#include "treasurehuntlib.h"

int main() {
    while (true) {
        int N, K;
        NextHunt(N, K);
        if (N == -1)
            return 0;

        // Dùng Query(x, y) để tìm K kho báu của lần tìm kiếm này.
    }
}

Dữ liệu vào

Không có standard input cho submission. Trước mỗi lần tìm kiếm, gọi NextHunt(N,K). Nếu không còn lần tìm kiếm nào, hàm gán \(N=K=-1\); khi đó phải kết thúc với mã thoát \(0\).

Dùng Query(x,y) với \(0\le x,y<N\). Hàm trả về TREASURE=0, hoặc tổng của các cờ DIR_RIGHT=1, DIR_UP=2, DIR_LEFT=4, DIR_DOWN=8. Không được gọi Query trước NextHunt, không được gọi Query hoặc NextHunt sau khi nhận \(-1\), không dùng tọa độ ngoài phạm vi, và không được hỏi quá \(1000\) lần trong một lần tìm kiếm.

Dữ liệu ra

Không có standard output. Một kho báu được tính là đã tìm khi Query ít nhất một lần tại đúng ô của nó. Có thể gọi NextHunt sớm để chuyển sang lần tìm kiếm kế tiếp; vi phạm giao thức gây RTE và nhận \(0\) điểm cho toàn bộ phân nhóm.

Ràng buộc

• \(2\le N\le10^6\), \(1\le K\le3\).
• Mỗi tiến trình có nhiều nhất \(100\,000\) lần tìm kiếm; mỗi lần có nhiều nhất \(1000\) truy vấn.
• Bộ chấm không thích nghi.

Phân nhóm

1. \(10\) điểm: \(K=1\).
2. \(30\) điểm: \(K=2\).
3. \(60\) điểm: \(K=3\).

Với một phân nhóm tổng \(S\) điểm, tất cả các lần tìm kiếm trong phân nhóm được xét cùng nhau. Nếu luôn tìm đủ kho báu, điểm là \(S/2+(S/2)\min_i f(Q_i/\lceil\log_2 N_i\rceil)\), trong đó \(f(t)=1\) khi \(t\le11\), \(f(t)=1-(t-11)/9\) khi \(11\le t\le20\), và \(f(t)=0\) khi \(t\ge20\). Nếu có lần chưa tìm đủ, điểm là \((S/2)\min_i(F_i/K_i)\). Kết quả không nguyên được làm tròn đến số nguyên gần nhất.

Ví dụ

Nguồn

CEOI 2026 - Ngày 1, bài Treasure Hunt.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.