# Bài 1: cstation

> Time limit: 1s
> Memory limit: 1GB

## Đề bài

Hệ thống đô thị của thành phố XYZ có thể được mô phỏng dưới dạng cây gồm $N$ đỉnh và $N-1$ cạnh. Mỗi đỉnh trên cây tương ứng với một khu vực, được đánh số từ $0$ đến $N-1$. Mỗi cạnh trên cây tương ứng với một con đường, được đánh số từ $0$ đến $N-2$. Trong đó, con đường thứ $i$ ($0\le i\le N-2$) nối trực tiếp hai khu vực $A_i$ và $B_i$.

Ban quy hoạch đô thị đã chọn ra $K$ tuyến đường để làm các **tuyến đường trọng điểm**. Các tuyến đường này được đánh số từ $0$ đến $K-1$. Trong đó, tuyến đường trọng điểm thứ $i$ ($0\le i\le K-1$) tương ứng với đường đi ngắn nhất xuất phát từ khu vực $U_i$ và kết thúc tại khu vực $V_i$.

Trong $Q$ ngày tiếp theo, mỗi ngày ban quy hoạch đô thị sẽ chọn ra một **tuyến đường tiềm năng**. Trong ngày thứ $i$ ($0\le i\le Q-1$), tuyến đường tiềm năng mà ban quy hoạch chọn sẽ là đường đi ngắn nhất xuất phát từ khu vực $X_i$ và kết thúc tại khu vực $Y_i$. Tuyến đường này trong ngày thứ $i$ sẽ được coi là **tuyến đường trọng điểm thứ $K$**. Khi kết thúc ngày, tuyến đường tiềm năng trong ngày đó sẽ không được coi là tuyến đường trọng điểm nữa.

Với mỗi ngày, ban quy hoạch muốn chọn ra một số khu vực trên đô thị và đặt trạm tại các khu vực đó sao cho:
- Với mọi tuyến đường trọng điểm được đánh số từ $0$ đến $K$, luôn có **ít nhất** một trạm được đặt trên các khu vực nằm trên tuyến đường đó.

**Lưu ý:** Ban quy hoạch chỉ muốn mô phỏng phương án đặt trạm. Trên thực tế, ban quy hoạch sẽ không xây dựng bất kỳ trạm nào trong suốt thời gian xét các tuyến đường tiềm năng.

**Yêu cầu:** Giả sử bạn là một thành viên của ban quy hoạch đô thị, hãy viết một chương trình để giải quyết vấn đề trên.

## Chi tiết cài đặt

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

vector<int> solve(int N, int K, int Q, const vector<int>& A, const vector<int>& B, const vector<int>& U, const vector<int>& V, const vector<int>& X, const vector<int>& Y);

- $N$: Số khu vực trên đô thị.
- $K$: Số tuyến đường trọng điểm ban đầu trên đô thị.
- $Q$: Số ngày cần xét tuyến đường tiềm năng.
- $A,B$: Hai mảng gồm $N-1$ phần tử, trong đó $A_i$ và $B_i$ ($0\le i\le N-2$) đại diện cho hai khu vực có con đường thứ $i$ nối trực tiếp trên đô thị.
- $U,V$: Hai mảng gồm $K$ phần tử, trong đó $U_i$ và $V_i$ ($0\le i\le K-1$) đại diện cho hai khu vực bắt đầu và kết thúc của tuyến đường trọng điểm thứ $i$.
- $X,Y$: Hai mảng gồm $Q$ phần tử, trong đó $X_i$ và $Y_i$ ($0\le i\le Q-1$) đại diện cho hai khu vực bắt đầu và kết thúc của tuyến đường tiềm năng ban quy hoạch chọn trong ngày thứ $i$.
- Hàm này cần trả về một mảng $ans$ bao gồm $Q$ phần tử, trong đó $ans_i$ ($0\le i\le Q-1$) là số trạm tối thiểu cần phải đặt nếu xét ngày thứ $i$.
- Hàm này sẽ được gọi $T$ lần, mỗi lần gọi tương ứng với một trường hợp thử nghiệm.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"cstationlib.h"` ở đầu.
- Trong chương trình, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm `main()`.

## Ràng buộc

- $1\le N,K,Q\le 10^5$
- $0\le A_i,B_i\le N-1$ với mọi $i$ từ $0$ đến $N-2$
- $0\le U_i,V_i\le N-1$ với mọi $i$ từ $0$ đến $K-1$
- $0\le X_i,Y_i\le N-1$ với mọi $i$ từ $0$ đến $Q-1$
- $A_i\ne B_i$ với mọi $i$ từ $0$ đến $N-2$
- $\sum_N,\sum_K,\sum_Q\le 2\times 10^5$

## Scoring

- Subtask $1$ ($5$ điểm): $1\le N,K,Q\le 14; T\le 50$
- Subtask $2$ ($10$ điểm): $\sum_N,\sum_K,\sum_Q\le 500$
- Subtask $3$ ($10$ điểm): $\sum_N,\sum_K,\sum_Q\le 3000$
- Subtask $4$ ($20$ điểm): $A_i=i,B_i=i+1$ với mọi $i$ từ $0$ đến $N-2$
- Subtask $5$ ($55$ điểm): Không có ràng buộc gì thêm

## Example

Khi trình chấm gọi hàm `solve(6, 2, 2, {0, 0, 0, 1, 2}, {1, 2, 5, 3, 4}, {3, 4}, {1, 2}, {5, 5}, {0, 1})` thì chương trình của bạn cần trả về kết quả là `{3, 2}`.

**Note:**
- Hệ thống đô thị sẽ có dạng như sau:


- Các tuyến đường trọng điểm ban đầu bao gồm các tuyến đường sau:
- $3\rightarrow 1$
- $4\rightarrow 2$
- Trong ngày thứ $0$, tuyến đường tiềm năng là tuyến đường $5\rightarrow 0$. Có thể đặt $3$ trạm tại các khu vực $3,4,5$ để thỏa mãn yêu cầu đề bài.
- Trong ngày thứ $1$, tuyến đường tiềm năng là tuyến đường $5\rightarrow 0\rightarrow 1$. Có thể đặt $2$ trạm tại các khu vực $1,2$ để thỏa mãn yêu cầu đề bài.
- Có thể chứng minh không có phương án nào cho ra kết quả tối ưu hơn.

# Bài 2: colorful

> Time limit: 2s
> Memory limit: 1GB

## Đề bài

Có một đống bóng gồm $N$ quả, các quả bóng được đánh số từ $0$ đến $N-1$. Mỗi quả bóng trong đống có thể có màu từ $0$ đến $K-1$, trong đó quả bóng thứ $i$ ($0\le i\le N-1$) có màu $A_i$ ($0\le A_i\le K-1$). Đảm bảo với mọi $j$ từ $0$ đến $K-1$, tồn tại ít nhất một quả bóng trong đống bóng có màu $j$.

**Lưu ý:** Bạn được biết trước giá trị của $N$, tuy nhiên bạn **không được biết chính xác** giá trị của $K$.

Bạn không biết trạng thái màu của các quả bóng trông thế nào, và bạn muốn tìm cách xác định nó. Để làm được việc này, bạn được phép thực hiện một số câu hỏi. Với mỗi câu hỏi:
- Bạn chọn một tập con gồm một số quả bóng trong $N$ quả.
- Sau đó, bạn sẽ biết được **số lượng màu khác nhau** xuất hiện trong các quả bóng được chọn có lớn hơn hoặc bằng $\lfloor \frac{K+1}2\rfloor$ hay không (trong đó, $\lfloor x\rfloor$ là số nguyên gần nhất nhỏ hơn hoặc bằng $x$).

**Yêu cầu:** Hãy viết một chương trình tương tác mô phỏng quá trình xác định màu của các quả bóng. Vì có thể có nhiều đáp án thỏa mãn khớp với câu trả lời của tất cả câu hỏi mà bạn có thể hỏi, bạn chỉ cần xác định một mảng trạng thái **đẳng cấu** với trạng thái gốc của các quả bóng. Cụ thể:
- Gọi $B_i$ là trạng thái màu của các quả bóng mà bạn dự đoán. Khi đó với mọi cặp số $(i,j)$ ($0\le i,j\le N-1,i\ne j$):
- Nếu $A_i=A_j$ thì $B_i=B_j$.
- Nếu $A_i\ne A_j$ thì $B_i\ne B_j$.
- **Ví dụ:** Hai mảng trạng thái `{0, 1, 2, 0, 0, 1}` và `{1, 2, 0, 1, 1, 2}` được xem như là **đẳng cấu** với nhau.

## Chi tiết cài đặt

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

vector<int> solve(int N);

- $N$: Số quả bóng trong đống bóng cho trước.
- **Lưu ý**: Bạn chỉ được biết giá trị của $N$ nhưng không được biết giá trị của $K$.
- Hàm này cần trả về một mảng $B$ tương ứng với trạng thái màu của các quả bóng mà bạn dự đoán. Đáp án của bạn cần phải đảm bảo các điều kiện như sau:
- $0\le B_i\le K-1$ với mọi $i$ từ $0$ đến $N-1$.
- $B$ **đẳng cấu** với $A$ ($A$ tương ứng với mảng lưu trạng thái ban đầu của các quả bóng mà bạn cần xác định).
- Hàm này được gọi nhiều lần, mỗi lần gọi tương ứng với một trường hợp thử nghiệm.

Trong hàm `solve()`, bạn được phép gọi hàm sau:

bool ask(vector<int> pos);

- $pos$: Một mảng bao gồm chỉ số của tất cả quả bóng được chọn. Cần phải đảm bảo các phần tử trong mảng $pos$ là các chỉ số quả bóng hợp lệ, và các giá trị trong mảng $pos$ phải đôi một phân biệt.
- Hàm này sẽ trả về `true` nếu như số màu khác nhau trong đống bóng được chọn lớn hơn hoặc bằng $\lfloor \frac{K+1}2\rfloor$, ngược lại hàm sẽ trả về `false`.
- Với mỗi trường hợp thử nghiệm, hàm `solve()` được gọi hàm `ask()` tối đa $14000$ lần.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"colorfullib.h"` ở đầu.
- Trong chương trình, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm `main()`.

## Ràng buộc

- $3\le K\le 32$
- $K\le N\le 256$
- $\sum_N\le 2\times 10^4$

## Scoring

- Subtask $1$ ($10$ điểm): $N\le 10;K\le 3$
- Subtask $2$ ($20$ điểm): $N\le 10$
- Subtask $3$ ($70$ điểm): Không có ràng buộc gì thêm

## Cách tính điểm

Nếu trong bất kỳ trường hợp thử nghiệm nào, chương trình của bạn trả về kết quả không thỏa mãn yêu cầu đề bài thì bạn sẽ không nhận được điểm cho test đó.

Ngược lại, gọi $P$ là số lần gọi hàm `ask()` tối đa trong tất cả lần gọi hàm `solve()` của một test. Khi đó điểm của bạn được tính như sau:

| Giá trị $P$ |Phần trăm số điểm|
|--------------------|-----------------|
| $P\le 1400$ | $100\%$ |
|$1400\le P\le 14000$|$\frac{1400}P\times 100\%$|
| $P>14000$ | $0\%$ |

Điểm của một subtask bằng phần trăm điểm tối thiểu của một test trong subtask đó nhân với số điểm tối đa của subtask.

# Bài 3: magician

> Time limit: 2s
> Memory limit: 1GB

## Đề bài

Hôm nay, Alice và Bob sẽ thực hiện một trò ảo thuật trước mặt hàng trăm khán giả. Trò ảo thuật mà hai người sẽ làm có thể được mô tả như sau:
- Đầu tiên, Bob bị bịt mắt, Alice gọi một khán giả bất kỳ lên. Khán giả sẽ chọn $N$ là bài trong bộ bài Tây $52$ lá Alice đã chuẩn bị.
- Từ $N$ lá bài, khán giả sẽ vẽ một cây **có gốc** gồm $N$ đỉnh, mỗi đỉnh tương ứng với một lá bài.
- Tiếp theo, Alice sẽ viết một số nguyên dương ở sau tất cả lá bài khán giả đã chọn.
- Sau đó, Alice sẽ xáo lại các lá bài và đưa cho Bob đống bài vừa xáo. Bob không được nhìn mặt trước của các lá bài mà chỉ được nhìn các số nguyên dương mà Alice đã viết trên đó.
- Từ dữ kiện trên, Bob sẽ dựng lại cây mà khán giả đã vẽ. Trò ảo thuật sẽ được coi là thành công nếu như cây mà Bob vẽ giống hệt với cây mà khán giả đã vẽ ban đầu. Cụ thể:
- Hai lá bài được chọn làm gốc phải giống hệt nhau.
- Các cặp lá bài có cạnh nối trực tiếp mô phỏng quan hệ cha-con trên cây cũng phải giống hệt nhau.
- **Lưu ý:** Nếu trên cây của khán giả, lá bài $A$ là cha của lá bài $B$ nhưng trên cây của Bob, lá bài $B$ là cha của lá bài $A$ thì hai cây sẽ không được coi là giống nhau.

Vì giới hạn kích thước của bảng, cây mà khán giả vẽ luôn đảm bảo có bậc tối đa nhỏ hơn hoặc bằng $8$ và số đỉnh tối đa có cùng bậc nhỏ hơn hoặc bằng $8$ $^\dagger$. Trong trò ảo thuật này, cây sẽ được mô phỏng dưới dạng một danh sách kề, mỗi đỉnh lưu trữ tất cả các con kề với đỉnh đó. Gốc của cây là đỉnh duy nhất không nằm trong danh sách kề của bất kỳ đỉnh nào.

Trò ảo thuật sẽ khiến mọi người càng bất ngờ nếu như giá trị lớn nhất mà Alice viết trên các lá bài càng nhỏ.

**Yêu cầu:** Hãy viết một chương trình mô phỏng lại trò ảo thuật của Alice và Bob.

$\dagger$: Trong cây, một đỉnh có bậc là $k$ nếu trên đường đi ngắn nhất từ gốc đến đỉnh đó có đúng $k$ cạnh. Bậc tối đa của cây được coi là bậc tối đa của các đỉnh trên cây đó.

## Chi tiết cài đặt

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

vector<int> solveAlice(vector<vector<int>> adj);

- $adj$: Một mảng hai chiều mô phỏng danh sách kề của cây mà khán giả đã vẽ. Trong đó:
- $N=|adj|$
- Các đỉnh trên cây được đánh số từ $0$ đến $N-1$, trong đó đỉnh thứ $i$ ($0\le i\le N-1$) tương ứng với lá bài thứ $i$
- Mỗi phần tử $adj_i$ ($0\le i\le N-1$) là một mảng lưu tất cả các **đỉnh con** kề với đỉnh $i$ trên cây mà khán giả đã vẽ
- Giá trị duy nhất không xuất hiện trên các mảng $adj_i$ là gốc của cây.
- $\sum_{|adj_i|}=N-1$
- Hàm này cần trả về một mảng $S$ gồm $N$ phần tử, trong đó $S_i$ ($0\le i\le N-1$) là số nguyên dương Alice đánh trên lá bài thứ $i$. Các số nguyên dương Alice viết không nhất thiết phải đôi một phân biệt.

vector<vector<int>> solveBob(vector<int> S);

- $S$: Một mảng gồm $N$ phần tử, trong đó $S_i$ ($0\le i\le N-1$) đại diện cho giá trị được viết trên lá bài thứ $i$ từ đống bài Alice đưa cho Bob. Các giá trị này có thể được sắp xếp lại theo một thứ tự bất kỳ, không nhất thiết phải theo thứ tự các giá trị xuất hiện trên mảng mà Alice đã trả về.
- Bob sẽ chỉ được biết các số được đánh trên các lá bài mà không được biết mặt trước các lá bài Alice đưa trông như thế nào.
- Hàm này cần trả về một mảng hai chiều tương ứng với danh sách kề của cây mà Bob vẽ. Danh sách kề này cần mô phỏng cây y hệt so với cây mà khán giả đã vẽ, với các chỉ số trong danh sách tương ứng với trình tự các lá bài mà Alice đã xáo.

**Lưu ý:**
- Chương trình sẽ gọi hai hàm liên tục $T$ lần, mỗi lần gọi tương ứng với một trường hợp thử nghiệm.
- Chương trình của bạn cần phải khai báo thư viện `"magicianlib.h"` ở đầu.
- Trong chương trình, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm `main()`.
- Với mỗi trường hợp thử nghiệm, hàm `solveAlice()` luôn được gọi trước hàm `solveBob()` và hai hàm này được gọi trên hai chương trình hoàn toàn độc lập.

## Ràng buộc

- $T\le 100$
- $N\le 32$
- Cấu trúc của cây luôn đảm bảo bậc tối đa của cây nhỏ hơn hoặc bằng $8$ và số đỉnh tối đa có cùng bậc nhỏ hơn hoặc bằng $8$

## Subtask

- Subtask $1$ ($10$ điểm): $N\le 9$, cây mà khán giả vẽ luôn đảm bảo là một đường thẳng
- Subtask $2$ ($90$ điểm): Không có ràng buộc gì thêm

## Cách tính điểm

Nếu trong bất kỳ trường hợp thử nghiệm nào, hàm `solveBob()` trả về danh sách kề không thỏa mãn với điều kiện đề bài, bạn sẽ không nhận được điểm cho test đó.

Ngược lại, gọi $M$ là số nguyên dương lớn nhất được viết trên các lá bài của Alice trong tất cả trường hợp thử nghiệm. Khi đó điểm của bạn được tính theo công thức như sau:

| Giá trị $M$ |Phần trăm số điểm|
|---------------|-----------------|
| $M\le 56$ | $100\%$ |
| $M=57$ | $80\%$ |
|$58\le M\le 88$| $(176-2M)\%$ |
| $M\ge 88$ | $0\%$ |

Điểm của một subtask bằng phần trăm điểm tối thiểu của một test trong subtask đó nhân với số điểm tối đa của subtask.

# Bài 4: sgame

> Time limit: 2s
> Memory limit: 1GB

## Đề bài

Alice có một dãy số $A$ gồm $N$ phần tử, các phần tử được đánh số từ $0$ đến $N-1$. Ban đầu, với mọi $i$ từ $0$ đến $N-1$, $A_i=i$. Alice có một danh sách gồm $M$ thao tác, được đánh số từ $0$ đến $M-1$. Với thao tác thứ $i$ ($0\le i\le M-1$):
- Alice sẽ chọn phần tử **có giá trị $H_i$** và chuyển nó về đầu dãy số. Các phần tử đứng trước $H_i$ sẽ lùi sang bên phải một vị trí.

Alice đưa hai dãy số $A$ và $H$ cho Bob, sau đó hỏi Bob $Q$ câu hỏi. Với câu hỏi thứ $i$ ($0\le i\le Q-1$):
- Alice đưa cho Bob ba số nguyên $L_i,R_i,P_i$.
- Alice sẽ thực hiện tất cả các thao tác theo thứ tự, nhưng không thực hiện các thao tác nằm trong đoạn $[L_i;R_i]$ **trên dãy ban đầu**.
- Bob cần xác định chính xác vị trí của phần tử có giá trị $P_i$ sau khi Alice đã thực hiện $M-(R_i-L_i+1)$ thao tác trên dãy ban đầu.

**Yêu cầu:** Cho hai dãy số $A,H$ và $Q$ câu hỏi, hãy giúp Bob viết một chương trình trả lời các câu hỏi do Alice đưa ra.

## Chi tiết cài đặt

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

vector<int> solve(int N, int M, int Q, const vector<int>& H, const vector<int>& L, const vector<int>& R, const vector<int>& P);

- $N$: Số lượng phần tử trong dãy số $A$.
- $M$: Số thao tác trong dãy thao tác $H$ của Alice.
- $Q$: Số câu hỏi Alice hỏi Bob.
- $H$: Mảng gồm $M$ phần tử, trong đó $H_i$ ($0\le i\le M-1$) đại diện cho giá trị của phần tử mà Alice sẽ dịch chuyển trong thao tác thứ $i$.
- $L,R$: Hai mảng gồm $Q$ phần tử, trong đó $L_i$ và $R_i$ ($0\le i\le Q-1$) đại diện cho đoạn truy vấn mà Alice sẽ không thực hiện khi xét câu hỏi thứ $i$.
- $P$: Mảng gồm $Q$ phần tử, trong đó $P_i$ ($0\le i\le Q-1$) đại diện cho giá trị của phần tử Bob cần xác định vị trí trong câu hỏi thứ $i$.
- Hàm này cần trả về một mảng $ans$ bao gồm $Q$ phần tử, trong đó $ans_i$ ($0\le i\le Q-1$) là đáp án của câu hỏi thứ $i$.
- Hàm này sẽ được gọi **một lần duy nhất** với mỗi test của bài.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"sgamelib.h"` ở đầu.
- Trong chương trình, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm `main()`.

## Ràng buộc

- $1\le N,M,Q\le 2\times 10^5$
- $0\le H_i\le N-1$ với mọi $i$ từ $0$ đến $M-1$
- $0\le L_i\le R_i\le M-1$ với mọi $i$ từ $0$ đến $Q-1$
- $0\le P_i\le N-1$ với mọi $i$ từ $0$ đến $Q-1$

## Scoring

- Subtask $1$ ($5$ điểm): $1\le N,M,Q\le 500$
- Subtask $2$ ($10$ điểm): $1\le N,M,Q\le 5000$
- Subtask $3$ ($33$ điểm): $\sum^{Q-1}_{i=0} R_i-L_i\le 2\times 10^5$
- Subtask $4$ ($52$ điểm): Không có ràng buộc gì thêm

## Ví dụ:

Khi trình chấm gọi hàm `solve(4, 3, 2, {2, 0, 3}, {1, 0}, {1, 0}, {1, 1})` thì chương trình của bạn cần trả về `{3, 2}`.

**Note:**

Xét câu hỏi đầu tiên, $L_i=1,R_i=1,H_i=1$. Quá trình thực hiện thao tác của Alice sẽ được mô tả như sau:
- Ban đầu, $A=\{0,1,2,3\}$.
- Alice thực hiện thao tác số $0$, sau thao tác $A=\{2,0,1,3\}$.
- Alice thực hiện thao tác số $2$, sau thao tác $A=\{3,2,0,1\}$.
- Alice không thực hiện thao tác số $1$ vì $1\in [1;1]$.

Vì vị trí của phần tử có giá trị $H_i=1$ là $3$ nên đáp án cho câu hỏi đầu tiên là $3$.

Xét câu hỏi thứ hai, $L_i=0,R_i=0,H_i=1$. Quá trình thực hiện thao tác của Alice sẽ được mô tả như sau:
- Ban đầu, $A=\{0,1,2,3\}$.
- Alice thực hiện thao tác số $1$, sau thao tác $A=\{0,1,2,3\}$.
- Alice thực hiện thao tác số $2$, sau thao tác $A=\{3,0,1,2\}$.
- Alice không thực hiện thao tác số $0$ vì $0\in [0;0]$.

Vì vị trí của phần tử có giá trị $H_i=1$ là $2$ nên đáp án cho câu hỏi thứ hai là $2$.

# Bài 5: vmachine

> Time limit: 2s
> Memory limit: 1GB

## Đề bài

Cho một cây gồm $N$ đỉnh và $N-1$ cạnh. Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Trong đó, cạnh thứ $i$ ($1\le i\le N-1$) nối trực tiếp giữa hai đỉnh $U_i$ và $V_i$, với $U_i$ là cha và $V_i$ là con.

Có một khe nhớ lưu trữ $2000$ số, các ô nhớ trong khe được đánh số từ $0$ đến $1999$, mỗi ô nhớ lưu trữ một số nguyên 16-bit (có thể có giá trị trong đoạn $[-32768;32767]$). Có thể coi khe nhớ đó là dãy số $A$ bao gồm $2000$ phần tử $A_0,A_1,\dots,A_{1999}$. Trong khe nhớ đó, thông tin về các cạnh trên cây ban đầu được lưu trữ như sau:
- Với mọi $i$ từ $1$ đến $N-1$, $A_{2i-2}=U_i,A_{2i-1}=V_i$.
- Với các ô nhớ còn lại, $A_i=0$.

Bạn cần viết ra một chương trình thao tác với các ô trong khe nhớ. Bạn được phép sử dụng các lệnh như sau:
- `print(i)`: In ra giá trị của $A_i$ ra màn hình.
- `sub(i,j,k)`: Thực hiện cập nhật $A_k:=A_i-A_j$.
- `mul(i,j,k)`: Thực hiện cập nhật $A_k:=A_i\times A_j$.
- `cmp(i,j,k)`: Thực hiện so sánh hai giá trị $A_i$ và $A_j$, nếu $A_i=A_j$ thì cập nhật $A_k:=1$. Ngược lại, cập nhật $A_k:=0$.

**Lưu ý:**
- Với mọi thao tác, các giá trị $i,j,k$ không nhất thiết phải đôi một phân biệt, nhưng phải thỏa mãn $0\le i,j,k\le 1999$.
- Chương trình của bạn không được truy cập vào các ô nhớ mà chỉ được thực hiện các lệnh đã được mô tả ở trên.
- Các phép toán thực hiện trên chương trình của bạn có thể xảy ra tràn số như một chương trình bình thường, nếu kết quả vượt quá kiểu dữ liệu `short` trong C++ (số nguyên 16-bit).

Chương trình của bạn cần phải thỏa mãn điều kiện sau:
- Chương trình cần in ra các số nguyên dương, trong đó các số phải có giá trị từ $1$ đến $N$, mỗi số nguyên dương được in ra duy nhất một lần.
- Xét thứ tự in các số, với mọi cặp đỉnh $(a,b)$ sao cho $a$ là cha của $b$ thì $a$ phải được in ra trước $b$.

**Yêu cầu:** Hãy viết một chương trình thực hiện yêu cầu của bài toán với những lệnh bạn được phép sử dụng.

## Chi tiết cài đặt

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

void solve(int N);

- $N$: Số đỉnh của cây bạn được cho trước.
- Hàm này cần mô tả cách mà chương trình của bạn hoạt động để thực hiện các yêu cầu của bài toán đã được mô tả ở trên.
- Hàm này được gọi $T$ lần trong một test, mỗi lần gọi tương ứng với một trường hợp thử nghiệm.

Trong hàm `solve()`, bạn được phép gọi các hàm sau:

void print(int i);

- $i$: Chỉ số của ô nhớ cần in ra. Cần phải đảm bảo $0\le i\le 1999$.
- Hàm này sẽ mô phỏng việc in ra giá trị của ô nhớ thứ $i$ ra màn hình.

void sub(int i, int j, int k);

- $i,j,k$: Chỉ số của các ô nhớ cần thiết để thực hiện thao tác cập nhật. Cần phải đảm bảo $0\le i,j,k\le 1999$ và các giá trị này không nhất thiết phải đôi một phân biệt.
- Hàm này sẽ thực hiện cập nhật $A_k:=A_i-A_j$.

void mul(int i, int j, int k);

- $i,j,k$: Chỉ số của các ô nhớ cần thiết để thực hiện thao tác cập nhật. Cần phải đảm bảo $0\le i,j,k\le 1999$ và các giá trị này không nhất thiết phải đôi một phân biệt.
- Hàm này sẽ thực hiện cập nhật $A_k:=A_i\times A_j$.

void cmp(int i, int j, int k);

- $i,j,k$: Chỉ số của các ô nhớ cần thiết để thực hiện thao tác cập nhật. Cần phải đảm bảo $0\le i,j,k\le 1999$ và các giá trị này không nhất thiết phải đôi một phân biệt.
- Hàm này sẽ thực hiện cập nhật $A_k:=1$ nếu $A_i=A_j$ và $A_k:=0$ trong trường hợp ngược lại.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"vmachinelib.h"` ở đầu.
- Với mỗi trường hợp thử nghiệm, chương trình của bạn được phép thực hiện tối đa $4\times 10^6$ lệnh.
- Trong chương trình, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm `main()`.

## Ràng buộc

- $T\le 50$
- $N\le 200$
- Độ dài của dãy $A$ (kích thước của khe nhớ) luôn bằng $2000$.

## Scoring

- Subtask $1$ ($7$ điểm): $N\le 10; A_{2i-2}=i,A_{2i-1}=i+1$ với mọi $i$ từ $1$ đến $N-1$.
- Subtask $2$ ($10$ điểm): $N\le 10$
- Subtask $3$ ($15$ điểm): $N\le 30$, với mọi đỉnh $i$ từ $1$ đến $N$ có tối đa một đỉnh con trực tiếp
- Subtask $4$ ($10$ điểm): $N\le 30$
- Subtask $5$ ($10$ điểm): $N\le 60$
- Subtask $6$ ($10$ điểm): $N\le 100$
- Subtask $7$ ($10$ điểm): $N\le 120$
- Subtask $8$ ($10$ điểm): $N\le 150$
- Subtask $9$ ($18$ điểm): Không có ràng buộc gì thêm

# Bài 6: festival

> Time limit: 1s
> Memory limit: 1GB

## Đề bài

Ở một vương quốc ABC, có một vị vua đang trị vì và cai quản $N$ người dân. Nhà vua muốn tổ chức một lễ hội ở ngoài vương quốc và cần đưa tất cả người dân ra khỏi vương quốc. Vì mỗi người cần làm các công việc khác nhau nên nhà vua đã bí mật đánh số các người dân từ $0$ đến $N-1$. Để đưa người dân ra khỏi vương quốc, nhà vua mỗi lần có thể chọn một số người để ra khỏi vương quốc cùng lúc, tuy nhiên mỗi lần nhà vua chỉ có thể chọn tối đa $S$ người cùng một lượt. Thêm vào đó, nhà vua có $K$ cặp số được đánh số từ $0$ đến $K-1$, trong đó cặp số thứ $i$ ($0\le i\le K-1$) là cặp số $(U_i,V_i)$ tương ứng với việc nhà vua muốn người dân $U_i$ phải ra khỏi vương quốc trước người dân $V_i$. Vì không muốn người dân hoảng loạn, nhà vua không cho những người dân trong vương quốc biết $K$ cặp số trên.

Nhà vua đã quyết định mời một nhà thông thái đến để giúp đỡ công việc trên sao cho mọi việc có thể diễn ra thuận lợi nhất có thể. Kế hoạch của họ như sau:
- Đầu tiên, nhà thông thái sẽ bàn bạc với những người dân để họ có phương án ra khỏi vương quốc thuận lợi. Lúc này nhà thông thái vẫn chưa biết giá trị của $K$ cặp số của nhà vua.
- Sau khi đã bàn bạc với người dân, nhà thông thái sẽ được biết giá trị của $K$ cặp số đó. Nhà thông thái cần chuẩn bị $N$ áo choàng tương ứng với $N$ người dân, mỗi chiếc áo choàng được nhà thông thái đánh một số nguyên dương.
- Tiếp theo, nhà thông thái sẽ phát $N$ chiếc áo choàng cho $N$ người dân tương ứng. Chiếc áo choàng rất kín, đảm bảo mỗi người dân chỉ có thể nhìn thấy số được đánh trên các chiếc áo choàng của những người dân khác **nhưng họ lại không thể thấy số được đánh trên áo của chính mình**. Những người dân không được bàn bạc và trao đổi với nhau trong suốt quá trình ra khỏi vương quốc.
- Nhà vua sẽ thực hiện $N$ lượt, ở mỗi lượt nhà vua sẽ hỏi tất cả người dân có ai muốn ra khỏi vương quốc trong lượt này không. Nhà vua sẽ chọn tất cả người dân muốn ra trong lượt này ra khỏi vương quốc. Trong một lượt có thể không ai ra khỏi vương quốc, nhưng cần đảm bảo mỗi lượt chỉ ra tối đa $S$ người cùng lúc và phải thỏa mãn điều kiện $K$ cặp số của nhà vua.

Kế hoạch được cho là thành công khi tất cả người dân có thể ra khỏi vương quốc thuận lợi. Nhà vua sẽ càng trầm trồ trước tài năng của nhà thông thái nếu số lớn nhất được đánh trên các áo choàng càng nhỏ càng tốt.

**Yêu cầu:** Hãy viết một chương trình mô phỏng lại quá trình nhà thông thái bàn bạc, chuẩn bị áo choàng và quá trình những người dân ra khỏi vương quốc sao cho số lớn nhất đuuợc đánh trên các áo choàng nhỏ nhất có thể.

## Chi tiết cài đặt

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

vector<int> solveGenius(int N, int S, const vector<int>& U, const vector<int>& V);

- $N$: Số lượng người dân trong vương quốc.
- $S$: Số lượng người dân tối đa có thể ra khỏi vương quốc cùng lúc trong một lượt.
- $U,V$: Hai mảng gồm $K=|U|=|V|$ phần tử, trong đó phần tử $U_i$ và $V_i$ ($0\le i\le K-1$) tương ứng với cặp số thứ $i$ của nhà vua.
- Hàm này cần trả về một mảng $S$ gồm $N$ phần tử, trong đó $S_i$ ($0\le i\le N-1$) là số nguyên dương được đánh trên chiếc áo choàng thứ $i$ mà nhà thông thái sẽ phát cho người dân thứ $i$.
- Hàm này được gọi **một lần duy nhất** với mỗi test.

bool solveCitizen(const vector<int>& A,const vector<vector<int>>& history);

- $A$: Một mảng gồm $N-1$ phần tử bao gồm các số được viết trên các chiếc áo choàng mà người dân tương ứng có thể nhìn thấy. Các phần tử trong dãy đã được sắp xếp tăng dần.
- $history$: Một `vector<vector<int>>` lưu lại lịch sử của các người dân đã ra khỏi vương quốc trong các lượt trước. Trong đó:
- $|history|$ là số lượt mà nhà vua đã thực hiện trước đó.
- Với mọi $i$ thỏa mãn $0\le i\le |history|-1$, $history_i$ lưu trữ số được viết trên áo choàng của những người dân đã ra khỏi vương quốc trong lượt thứ $i+1$. Các giá trị trong mảng $history_i$ được sắp xếp tăng dần.
- Hàm này cần trả về `true` nếu như người dân này quyết định ra khỏi vương quốc trong lượt thứ $|history|+1$ và trả về `false` trong trường hợp ngược lại.
- Hàm này sẽ được gọi $N^2$ lần sau khi hàm `solveGenius()` được gọi, mỗi lần gọi tương ứng với việc kiểm tra một người dân có ra khỏi vương quốc trong một lượt cụ thể không.

**Lưu ý:**
- Chương trình của bạn cần phải khai báo thư viện `"festivallib.h"` ở đầu.
- Trong chương trình, thí sinh được phép cài đặt các biến, các hàm toàn cục, nhưng không được phép có hàm `main()`.
- Trình chấm sẽ gọi `solveGenius()` trước, sau đó mới gọi nhiều lần hàm `solveCitizen()` để mô phỏng quá trình nhà vua đưa những người dân ra khỏi vương quốc. Hai hàm này được gọi trên hai chương trình hoàn toàn độc lập.

## Ràng buộc

- $2\le N\le 200$
- $1\le S\le N$
- $0\le K<\frac{N\times (N-1)}2$
- Đảm bảo luôn tồn tại phương án để những người dân có thể ra khỏi vương quốc

## Scoring

- Subtask $1$ ($10$ điểm): $N=2$
- Subtask $2$ ($20$ điểm): Với mọi $v$ từ $0$ đến $N-1$, tồn tại **tối đa** một cặp số có dạng $(u,v)$ trong $K$ cặp số
- Subtask $3$ ($20$ điểm): $S=2$
- Subtask $4$ ($50$ điểm): Không có ràng buộc gì thêm

## Cách tính điểm

Nếu trong quá trình người dân ra khỏi vương quốc xảy ra mâu thuẫn, bạn sẽ không nhận được điểm cho test đó.

Ngược lại, gọi $P$ là số lớn nhất được viết trên các áo choàng theo cách giải của bạn và $J$ là số lớn nhất được viết trên các áo choàng theo cách giải của giám khảo. Gọi $D=P-J$. Khi đó điểm của bạn được tính theo công thức như sau:

| Giá trị $D$ |Phần trăm số điểm|
|---------------|-----------------|
| $D\le 0$ | $100\%$ |
| $D=1$ | $80\%$ |
| $D=2$ | $60\%$ |
| $3\le D\le N$ |$\frac{1}{D-1}\times 100\%$|
| $D>N$ | $0\%$ |

Điểm của một subtask bằng phần trăm điểm tối thiểu của một test trong subtask đó nhân với số điểm tối đa của subtask.