Priglavci
레이팅 미적용의견: 0
2 \(s / 64\) \(MB / 160\) points
Engineer Zlatko got assigned the task of checking the quality of transportation for students
getting to school by bus. In a 2\(D-co\)ordinate system, there are \(N\) students with coordinates \(u\) _{x}
and \(u\) {y}{ }, and \(M\) bus stops with coordinates \(s\) {x} and \(s\) . At the beginning, a field can be occupied}_{
by one student or by one stop, or it can be empty.
Also, engineer Zlatko has a list of \(K\) bus lines: for each bus line, he has a list of stops the bus
stops at in the order in which the stops are listed. One stop belongs exclusively to one bus
line. The stops are distinct within a bus line. There is only one bus per line. Additionally,
each bus can fit \(C\) students. Bus stops don’t have a limit on the number of students that
could be waiting for it.
When a student boards a bus, they don’t get off until the end of the ride when the bus has
stopped at all stops of the line. A student can board only one bus. For a student to board a
bus, they must reach a stop of one of the bus lines. The length of the path which a student
walked from their position to a bus stop is measured as the squared Euclidean distance: (u _{x}
- s {x}{ }) {2}{ } + (u {y}{ } - s {y}{ }) {2}{ }.
Engineer Zlatko chooses the boarding stop for each student and distributes them so that the
buses can fit everyone, respecting the given limitations. The weakness of the distribution of
students is measured as the distance walked by the student farthest from their boarding bus
stop.
Help engineer Zlatko and calculate the minimal possible weakness and the distribution of
students.
In test cases worth 50% of total points, it will hold \(C = 1\) .
In test cases worth additional 30% of total points, it will hold \(1 \le C \le 10\).
The first line of input contains integers N, M, C, K ( \(1 \le N\), M, C, K ≤ 100 ) from the task.
Each of the following \(N\) lines contains integers \(u\) {x} and \(u\) ( -\(1000 \le u\) {x}{ }, u _{y} ≤1000 ), the students’
coordinates.
Each of the following \(M\) lines contains integers \(s\) {x} and \(s\) ( -\(1000 \le s\) {x}{ }, \(s\) _{y} ≤1000 ), the stops’
coordinates.
Each of the following \(K\) lines contains the list of bus stops: first, the number of stops K _{i} of the
bus line, then K {i}{ } numbers \(st\) {j}{ } (1 ≤ \(st\) {j}{ } ≤ \(M\) ) that denote the stops.
If it is possible to distribute the students within the requirements, you must output the
required weakness in the first line, and in the following \(N\) lines, the \(i\) ^{th} line must contain the
stop the \(i\) ^{th} student must walk to. In the case that the distribution of students to bus stops with
the calculated weakness is not unique, output an arbitrary distribution with such weakness.
If it is impossible to distribute the students, you must output ‘-1’ (without quotes).
2 \(s / 64\) \(MB / 160\) points
2 1 2 1
2 1
2 5
2 3
1 1
2 1 1 1
2 1
2 5
2 3
1 1
3 3 2 2
1 3
2 2
8 7
3 4
6 7
8 4
2 1 2
1 3output
output
4
1
1
-1
9
1
1
3Clarification of the first test case:
The distance which both students must walk to a bus stop is 2. The squared value of that instance is
4.
Clarification of the second test case:
Since only one line exists, in total there is a single bus with a capacity of 1, which is not sufficient to
distribute all the students properly.
Clarification of the third test case:
Firstly, two students go to the first stop. The nearest stop to the third student is the second stop, but
that stop belongs to the bus line of an already full bus. Therefore, the third student must go to the third
stop, and the squared value of their path length is 9. Every other distribution results in greater
weakness.
평가 및 의견
Priglavci
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Priglavci