Tree Boxes-无交互

交互题

题目描述:

Farmer John计划建造N（1≤N≤105）个农场，由N−1N−1条道路连通，构成一棵树。通常，当他的一个农场出现问题时，他不会被告知具体出现了问题的农场。取而代之的是，他会被告知从某个农场A到某个农场B的路径上的农场之一出现了问题。这经常使Farmer John感到困惑，因为他平时都驾驶越野拖拉机，所以对道路系统并不熟悉。

Farmer John将农场的位置视为二维坐标系中的点。他更希望被告知出现问题的是某个四边平行于坐标轴的长方形区域中的某个农场。这样Farmer John就可以自己决定如何在农场之间通行。Bessie告诉他这有些太困难了，所以只要他被告知两个不包含相同农场并且总共包含了沿A到B路径上的所有农场的四边与坐标轴平行的长方形，他就满意了。你需要帮助Farmer John决定他应当建造他的农场的位置，使得这一条件被满足。

这是一道交互题，你不可以使用标准（或文件）输入输出。 使用标准（或文件）输入输出的程序将会被取消成绩。 然而，你可以使用全局或是静态变量。为了帮助Farmer John，你需要实现如下函数：

 

  • void addRoad(int A, int B)：处理一条建造在农场AA和BB之间的道路（0≤A,B≤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应当将农场ID（0≤ID≤N−1）建造在位置(X,Y)，其中1≤X,Y≤105。应当仅被1≤X,Y≤105。应当仅被buildFarms调用。
  • void addBox(int X1, int Y1, int X2, int Y2)：增加一个告知Farmer John的长方形，其中1≤X1≤X2≤105， 1≤Y1≤Y2≤105。应当仅被JnotifyFJ调用。

交互方式如下。首先，addRoad会被调用N−1次，用来告知你的程序道路系统。接下来，buildFarms会被调用，你需要确定Farmer John需要建造每个农场的位置，并且相应地为每个农场调用setFarmLocation。最后，会有Q次对JnotifyFJ的调用，在每次调用中你必须调用一次或两次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)

选手程序调用addBox(1,1,1,2)

选手程序调用addBox(2,2,2,2)

选手程序结束notifyFJ(0,2)

评测结束，选手程序通过测试用例

时间限制: 1000ms
空间限制: 512MB

来源: USACO 2019 OPEN Platinum