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)$