oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

communication Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

communication.html

The country of JOI exists on a plane. Within the country, there are N villages numbered from 1 to N. Village i is located at (i, 0). Currently, the country of JOI is in the process of establishing a communication system that connects the N villages. To reduce the probability of failure, two communication systems will be built. These will be called system 1 and system 2.

In system k, there are Mk hubs and N + Mk - 1 communication lines. The hubs in system k are numbered from 1 to Mk. Hub j from system k is located at (Xkj, Ykj). Each communication line in system k is a straight line that connects a system k hub and another system k hub or one of the N villages. It is guaranteed that any pair of communication lines will not share any common point aside from their endpoints. For each hub j in system 1, its y-coordinate Y1j is greater than 0. For each hub j in system 2, its y-coordinate Y2j is less than 0.

We will call a pair of points connected if they are connected by a set of communication lines. In other words, two points are connected if, moving along communication lines between points on the plane, it is possible to move from either of the points to the other. The villages are connected with respect to system 1. In other words, considering only the communication lines and hubs in system 1, any pair of the N villages are connected. Similarly, the villages are also connected with respect to system 2.

The following diagram shows several possible layouts of the country's communication systems. Grey circles are system 1 hubs and black circles are system 2 hubs. The white circles represent the villages.

Figure 1: Example communication system 1

Figure 2: Example communication system 2

To evaluate several possible plans for the system's layout, we will investigate the resilience of the proposed communication system to external attacks. Each attack on the communication system can be expressed by two integers A and B (A ≥ 0, B ≤ 0), which indicate that all hubs with y-coordinate greater than A or less than B are destroyed. It is not possible to communicate between two communication lines if the hub joining them has been destroyed.

Given the proposed layout of the communication system, you are to answer Q queries about it. Query q is represented by one integer Aq. This means that all hubs with y-coordinate greater than Aq are destroyed. For each query, determine an integer Bq (Bq ≤ 0) such that even if all hubs with y-coordinate less than Bq are also destroyed, the N villages are still connected. If there are multiple such Bq, output the largest possible value of Bq.

Input

Read from standard input.

  • On the first line, there are four integers, N, M1, M2 and Q.
  • The next M1 + (N + M1 - 1) lines describe system 1:

    • On the ith line of the first M lines, there are two integers, X1i and Y1i.
    • On the ith line of the next N + M1 - 1 lines, there are three integers, T1i, C1i and D1i (T1i = 1 or T1i = 2).
      • If T1i is 1, the ith communication line connects village C1i to communication hub D1i (1 ≤ C1i ≤ N and 1 ≤ D1i ≤ M1).
      • If T1i is 2, the ith communication line connects communication hubs C1i an D1i (1 ≤ C1i ≤ M1 and 1 ≤ D1i ≤ M1 and C1i ≠ D1i).
  • The next M2 + (N + M2 - 1) lines describe system 2:

    • On the ith line of the first M lines, there are two integers, X2i and Y2i.
    • On the ith line of the next N + M2 - 1 lines, there are three integers, T2i, C2i and D2i (T2i = 1 or T2i = 2).
      • If T2i is 1, the ith communication line connects village C2i to communication hub D2i (1 ≤ C2i ≤ N and 1 ≤ D2i ≤ M2).
      • If T2i is 2, the ith communication line connects communication hubs C2i an D2i (1 ≤ C2i ≤ M2 and 1 ≤ D2i ≤ M2 and C2i ≠ D2i).
  • On the qth line of the next Q lines, there is one integer, Aq (1 ≤ Aq ≤ Q).

Output

Print to standard output.

For each query q of the Q queries, print one integer Bq on one line, representing the answer to the query. If the answer is 0, you are not allowed to output -0.

Constraints

All test cases satisfy the following constraints:

  • 1 ≤ N, M1, M2 ≤ 100 000.
  • -1 000 000 000 ≤ X1i ≤ 1 000 000 000 (1 ≤ i ≤ M1).
  • -1 000 000 000 ≤ X2i ≤ 1 000 000 000 (1 ≤ i ≤ M2).
  • 1 ≤ Y1i ≤ 1 000 000 000 (1 ≤ i ≤ M1).
  • -1 000 000 000 ≤ Y2i ≤ -1 (1 ≤ i ≤ M2).
  • X1i ≠ X1j or Y1i ≠ Y1j (1 ≤ i, j ≤ M1 and i ≠ j).
  • X2i ≠ X2j or Y2i ≠ Y2j (1 ≤ i, j ≤ M2 and i ≠ j).
  • 1 ≤ Q ≤ 100 000.
  • 0 ≤ Aq ≤ 1 000 000 000 (1 ≤ q ≤ Q).
  • No two distinct communication lines will share points other than their endpoints.
  • The villages are connected with respect to system 1 and also with respect to system 2.

Subtasks

Subtask 1 (20 points):

The following constraints are satisfied.

  • N, M1, M2 ≤ 1 000.
  • Q ≤ 1 000.

Subtask 2 (80 points):

No further constraints.

Sample Input 1

4 3 3 1
1 1
3 2
2 3
1 1 1
1 2 1
1 3 2
1 4 2
2 1 3
2 2 3
3 -1
2 -2
1 -3
1 1 3
1 2 2
1 3 1
1 4 1
2 1 2
2 2 3
2

Sample Output 1

-2

This test case is corresponds to Figure 1 above.

Sample Input 2

6 4 5 4
2 1
4 1
3 3
5 2
1 1 1
1 2 1
1 3 2
1 4 2
2 2 4
1 5 4
1 6 4
2 1 3
2 4 3
3 -3
5 -1
2 -2
2 -1
4 -2
1 2 4
1 3 4
1 1 4
2 1 3
1 5 2
1 6 2
1 4 5
2 2 5
1 3 1
2 5 1
3
1
2
0

Sample Output 2

0
-2
-1
-3

This test case corresponds to Figure 2 above.

communication2.jpg

communication1.jpg

Tags

JOI 2012/2013

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
120261s256MBMinimum
280261s256MBMinimum
3021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o communication -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.