Home » 國際競賽 » Details

USACO 2019 US Open Contest, Platinum Problem 1. Tree Boxes

Category: 國際競賽, 計算機國際競賽 Date: 2019年5月17日下午6:32

Farmer John is planning to build? $N$ ?( $1 \leq N \leq 10^{5}$ ) farms that will be connected by? $N ? 1$ ?roads, forming a tree. Typically, whenever one of his farms is having an issue he is not told the specific farm that is having an issue. Instead, he is told that one of the farms along the path from some farm? $A$ ?to another farm? $B$ ?is having an issue. This is often confusing for Farmer John, as he usually drives offroad tractors and isn't familiar with the road system.

Farmer John considers the location of a farm to be a 2D point. He would prefer to be told that there is a problem in one of the farms in a specified axis-aligned rectangular box. This way Farmer John can decide for himself how to navigate between the farms. Bessie told him that this is a little too ambitious, so he will be satisfied if he is notified with at most two axis-aligned rectangular boxes whose intersection (of farms) is empty and whose union is exactly the farms along the path from? $A$ ?to? $B$ . You must help Farmer John determine where he should build his farms such that this condition is satisfied.

This is an interactive problem, you will not be using standard (or file) I/O.?Solutions that use standard (or file) I/O will be disqualified.?However, you ARE ALLOWED to use global and static variables. You must implement the following functions to help Farmer John:

void addRoad(int A, int B): processes a road between farms? $A$ ?and? $B$ ?( $0 \leq A, B \leq N ? 1$ ).
void buildFarms(): determines where Farmer John should build all his farms.
void notifyFJ(int A, int B): notifies Farmer John with either one or two boxes that satisfy the aforementioned conditions.

Your implementation of the above functions will be able to call the functions given below. You may assume that? $notifyFJ$ ?will be called? $Q$ ?times ( $1 \leq Q \leq 10^{5}$ ).

int getN(): gets the value of? $N$ .
int getQ(): gets the value of? $Q$ .
void setFarmLocation(int ID, int X, int Y): determines that Farmer John should build farm? $I D$ ?( $0 \leq I D \leq N ? 1$ ) at location? $(X, Y)$ ?where? $(1 \leq X, Y \leq N)$ . Should only be called from? $buildFarms$ .
void addBox(int X1, int Y1, int X2, int Y2): adds a box to notify Farmer John where? $(1 \leq X 1 \leq X 2 \leq N)$ ?and? $(1 \leq Y 1 \leq Y 2 \leq N)$ . Should only be called from? $notifyFJ$ .

The interactive protocol works as follows. First,? $addRoad$ ?will be called? $N ? 1$ ?times, to inform your program of the road system. Then,? $buildFarms$ ?will be called and you must determine where Farmer John should build each farm and call? $setFarmLocation$ for every farm accordingly. Finally, there will be? $Q$ ?calls to? $notifyFJ$ ?where you must make either one or two calls to? $addBox$ ?to notify Farmer John.

It is guaranteed there is always a valid way to notify Farmer John using either one or two boxes. The memory limit for this problem is set to 512MB, above the usual 256MB limit.

For a C++ solution, use this template:

#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
}

For a Java solution, use this template:

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
  	}
}

Sample Interaction

Grader calls? $addRoad(0,1)$

Grader calls? $addRoad(1,2)$

Grader calls? $buildFarms()$

Solution calls? $setFarmLocation(0,1,1)$

Solution calls? $setFarmLocation(1,1,2)$

Solution calls? $setFarmLocation(2,2,2)$

Solution ends? $buildFarms()$

Grader calls? $notifyFJ(0,0)$

Solution calls? $addBox(1,1,1,1)$

Solution ends? $notifyFJ(0,0)$

Grader calls? $notifyFJ(0,2)$

Solution calls? $addBox(1,1,1,2)$

Solution calls? $addBox(2,2,2,2)$

Solution ends? $notifyFJ(0,2)$

Grader terminates, and solution passes test-case

(Note: if you do not pass the first test case, the grader will indicate this as usual. However, note that the short sample interaction above does not correspond to the first test case or any other).

Problem credits: Spencer Compton

中文版

Farmer John計劃建造 $N$ （ $1 \leq N \leq 10^{5}$ ）個農場，由 $N ? 1$ 條道路連通，構成一棵樹。通常，當他的一個農場出現問題時，他不會被告知具體出現了問題的農場。取而代之的是，他會被告知從某個農場 $A$ 到某個農場 $B$ 的路徑上的農場之一出現了問題。這經常使Farmer John感到困惑，因為他平時都駕駛越野拖拉機，所以對道路系統并不熟悉。

Farmer John將農場的位置視為二維坐標系中的點。他更希望被告知出現問題的是某個四邊平行于坐標軸的長方形區域中的某個農場。這樣Farmer John就可以自己決定如何在農場之間通行。Bessie告訴他這有些太困難了，所以只要他被告知兩個不包含相同農場并且總共包含了沿 $A$ 到 $B$ 路徑上的所有農場的四邊與坐標軸平行的長方形，他就滿意了。你需要幫助Farmer John決定他應當建造他的農場的位置，使得這一條件被滿足。

這是一道交互題，你不可以使用標準（或文件）輸入輸出。?使用標準（或文件）輸入輸出的程序將會被取消成績。?然而，你可以使用全局或是靜態變量。為了幫助Farmer John，你需要實現如下函數：

void addRoad(int A, int B)：處理一條建造在農場 $A$ 和 $B$ 之間的道路（ $0 \leq A, B \leq N ? 1$ ）。
void buildFarms()：確定Farmer John需要建造所有農場的位置。
void notifyFJ(int A, int B)：告知Farmer John滿足前述條件的一個或兩個長方形。

你對上述函數的實現中可以調用下面給出的函數。假設 $notifyFJ$ 會被調用 $Q$ 次。

int getN()：獲得 $N$ 的值。
int getQ()：獲得 $Q$ 的值。
void setFarmLocation(int ID, int X, int Y)：決定Farmer John應當將農場 $I D$ （ $0 \leq I D \leq N ? 1$ ）建造在位置 $(X, Y)$ ，其中 $1 \leq X, Y \leq 10^{5} 。應當僅被$ texttt{buildFarms}$調用。
void addBox(int X1, int Y1, int X2, int Y2)：增加一個告知Farmer John的長方形，其中 $1 \leq X 1 \leq X 2 \leq 10^{5}$ ，? $1 \leq Y 1 \leq Y 2 \leq 10^{5}$ 。應當僅被 $notifyFJ$ 調用。

交互方式如下。首先， $addRoad$ 會被調用 $N ? 1$ 次，用來告知你的程序道路系統。接下來， $buildFarms$ 會被調用，你需要確定Farmer John需要建造每個農場的位置，并且相應地為每個農場調用 $setFarmLocation$ 。最后，會有 $Q$ 次對 $notifyFJ$ 的調用，在每次調用中你必須調用一次或兩次 $addBox$ 來告知Farmer John。

保證始終存在一種符合條件的方式可以使用一個或兩個長方形來告知Farmer John。這個問題的運行內存限制為512MB，超過一般問題所給的256MB內存限制。

C++的程序請使用下面的模板：

#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
}

Java的程序請使用下面的模板：

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
    }
}

交互樣例：

評測機調用 $addRoad(0,1)$

評測機調用 $addRoad(1,2)$

評測機調用 $buildFarms()$

選手程序調用 $setFarmLocation(0,1,1)$

選手程序調用 $setFarmLocation(1,1,2)$

選手程序調用 $setFarmLocation(2,2,2)$

選手程序結束 $buildFarms()$

評測機調用 $notifyFJ(0,0)$

選手程序調用 $addBox(1,1,1,1)$

選手程序結束 $notifyFJ(0,0)$

評測機調用 $notifyFJ(0,2)$