Farmer John dự định xây dựng \(N\) trang trại (\(1 \leq N \leq 10^5\)), được nối với nhau bằng \(N-1\) con đường tạo thành một cây. Thông thường, mỗi khi một trang trại của ông gặp sự cố, ông không được cho biết cụ thể trang trại nào đang gặp sự cố. Thay vào đó, ông được thông báo rằng một trong các trang trại trên đường đi từ một trang trại \(A\) tới một trang trại khác \(B\) đang gặp sự cố. Điều này thường khiến Farmer John bối rối, vì ông thường lái máy kéo địa hình và không quen thuộc với hệ thống đường sá.

Farmer John coi vị trí của một trang trại là một điểm 2D. Ông muốn được thông báo rằng có sự cố tại một trong những trang trại nằm trong một hình chữ nhật có các cạnh song song với trục tọa độ được chỉ định. Bessie nói với ông rằng yêu cầu này hơi quá tham vọng, nên ông sẽ hài lòng nếu được thông báo bằng nhiều nhất hai hình chữ nhật có các cạnh song song với trục tọa độ, sao cho giao của chúng (xét trên tập các trang trại) là rỗng và hợp của chúng đúng bằng tập các trang trại trên đường đi từ \(A\) tới \(B\). Bạn phải giúp Farmer John xác định vị trí xây các trang trại sao cho điều kiện này được thỏa mãn.

Đây là một bài tương tác; bạn sẽ không sử dụng vào/ra chuẩn (hoặc vào/ra tệp). Những lời giải sử dụng vào/ra chuẩn (hoặc vào/ra tệp) sẽ bị loại. Tuy nhiên, bạn ĐƯỢC PHÉP sử dụng biến toàn cục và biến tĩnh. Bạn phải cài đặt các hàm sau để giúp Farmer John:

• void addRoad(int A, int B): xử lý một con đường giữa trang trại \(A\) và \(B\) (\(0 \le A, B \le N - 1\)).
• void buildFarms(): xác định nơi Farmer John nên xây tất cả các trang trại.
• void notifyFJ(int A, int B): thông báo cho Farmer John bằng một hoặc hai hình chữ nhật thỏa mãn các điều kiện nêu trên.

Phần cài đặt các hàm trên của bạn có thể gọi các hàm được cung cấp dưới đây. Bạn có thể giả sử rằng \(\texttt{notifyFJ}\) sẽ được gọi \(Q\) lần (\(1 \leq Q \leq 10^5\)).

• int getN(): lấy giá trị của \(N\).
• int getQ(): lấy giá trị của \(Q\).
• void setFarmLocation(int ID, int X, int Y): xác định rằng Farmer John nên xây trang trại \(ID\) (\(0 \le ID \le N-1\)) tại vị trí \((X,Y)\), trong đó \((1 \le X, Y \le N)\). Chỉ được gọi từ \(\texttt{buildFarms}\).
• void addBox(int X1, int Y1, int X2, int Y2): thêm một hình chữ nhật vào thông báo cho Farmer John, trong đó \((1 \le X1 \le X2 \le N)\) và \((1 \le Y1 \le Y2 \le N)\). Chỉ được gọi từ \(\texttt{notifyFJ}\).

Giao thức tương tác

Giao thức tương tác hoạt động như sau. Đầu tiên, \(\texttt{addRoad}\) sẽ được gọi \(N-1\) lần để thông báo cho chương trình của bạn về hệ thống đường sá. Sau đó, \(\texttt{buildFarms}\) sẽ được gọi; bạn phải xác định nơi Farmer John nên xây từng trang trại và gọi \(\texttt{setFarmLocation}\) tương ứng cho mọi trang trại. Cuối cùng, sẽ có \(Q\) lời gọi tới \(\texttt{notifyFJ}\); với mỗi lời gọi, bạn phải gọi \(\texttt{addBox}\) một hoặc hai lần để thông báo cho Farmer John.

Đảm bảo rằng luôn có một cách hợp lệ để thông báo cho Farmer John bằng một hoặc hai hình chữ nhật. Giới hạn bộ nhớ cho bài này được đặt là 512 MB, cao hơn giới hạn thông thường 256 MB.

Mẫu C++

Với lời giải C++, hãy sử dụng mẫu sau:

#include "grader.h"

void addRoad(int a, int b){
    // Fill in code here
}

void buildFarms(){
    // Fill in code here
}

void notifyFJ(int a, int b){
    // Fill in code here
}

Mẫu Java

Với lời giải Java, hãy sử dụng mẫu sau:

import java.io.IOException;
// If you find it necessary, you may import other standard libraries here.
public class boxes extends Grader {

    // Copy this exactly:

@Override
    public static void main(String args[]) throws IOException { new boxes().run(); }


@Override
    public void addRoad(int a, int b) {
      // Fill in code here
    }

@Override
    public void buildFarms(){
      // Fill in code here
      }

@Override
    public void notifyFJ(int a, int b){
      // Fill in code here
    }
}

Tương tác mẫu

Trình chấm gọi \(\texttt{addRoad(0,1)}\).

Trình chấm gọi \(\texttt{addRoad(1,2)}\).

Trình chấm gọi \(\texttt{buildFarms()}\).

Lời giải gọi \(\texttt{setFarmLocation(0,1,1)}\).

Lời giải gọi \(\texttt{setFarmLocation(1,1,2)}\).

Lời giải gọi \(\texttt{setFarmLocation(2,2,2)}\).

Lời giải kết thúc \(\texttt{buildFarms()}\).

Trình chấm gọi \(\texttt{notifyFJ(0,0)}\).

Lời giải gọi \(\texttt{addBox(1,1,1,1)}\).

Lời giải kết thúc \(\texttt{notifyFJ(0,0)}\).

Trình chấm gọi \(\texttt{notifyFJ(0,2)}\).

Lời giải gọi \(\texttt{addBox(1,1,1,2)}\).

Lời giải gọi \(\texttt{addBox(2,2,2,2)}\).

Lời giải kết thúc \(\texttt{notifyFJ(0,2)}\).

Trình chấm kết thúc và lời giải vượt qua trường hợp kiểm thử.

Lưu ý: nếu bạn không vượt qua trường hợp kiểm thử đầu tiên, trình chấm sẽ thông báo điều này như thường lệ. Tuy nhiên, lưu ý rằng phần tương tác mẫu ngắn ở trên không tương ứng với trường hợp kiểm thử đầu tiên hay bất kỳ trường hợp kiểm thử nào khác.

Nguồn

USACO 2019 US Open Contest, Platinum — Tree Boxes

Tác giả: Spencer Compton.