RTE '16 S3 - School Traversal - DMOJ: Modern Online Judge

RTE '16 S3 - School Traversal

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.8s

Memory limit: 256M

Author:

Callum

Problem type

Ellen is a student at RHHS who is trying to navigate her way through the school to get to her classes. She knows that most halls are going to be blocked off by large groups of aimless students, so she has devised a map of the school which only includes hallways she knows will be open. In particular, the school can be represented as a collection of $N$ $N$ classrooms numbered $0$ $0$ to $N-1$ $N - 1$ with $N-1$ $N - 1$ hallways between them. It is guaranteed that these hallways will never form a loop.

Because Ellen is travelling around the school a lot, she wants to know how far it is between different locations in the school, so she can plan how long it will take to walk between them.

To help her with this, you will be given $Q$ $Q$ queries; for each one, you must determine the distance between the two given classrooms.

Input Specification

The first line will contain $N$ $N$ $(3 \le N \le 6\,000)$ $(3 \leq N \leq 6 000)$ , the number of classrooms.

The next $N-1$ $N - 1$ lines will contain three space-separated integers, $a_i$ $a_{i}$ , $b_i$ $b_{i}$ , $w_i$ $w_{i}$ $(0 \le a_i,b_i \le N-1, 1 \le w_i \le 500\,000)$ $(0 \leq a_{i}, b_{i} \leq N - 1, 1 \leq w_{i} \leq 500 000)$ , indicating that there is a hallway between classrooms $a_i$ $a_{i}$ and $b_i$ $b_{i}$ with length $w_i$ $w_{i}$ .

The next line will contain $Q$ $Q$ $(1 \le Q \le 1\,000\,000)$ $(1 \leq Q \leq 1 000 000)$ , the number of queries to be answered.

The next $Q$ $Q$ lines will contain two space-separated integers, $u_i$ $u_{i}$ and $v_i$ $v_{i}$ $(0 \le u_i, v_i \le N-1)$ $(0 \leq u_{i}, v_{i} \leq N - 1)$ , representing a query that asks the distance between classrooms $u_i$ $u_{i}$ and $v_i$ $v_{i}$ .

For test cases worth 20 of 100 points, $3 \le N \le 500$ $3 \leq N \leq 500$ and $1 \le Q \le 10\,000$ $1 \leq Q \leq 10 000$ .

For test cases worth an additional 20 points, $3 \le N \le 500$ $3 \leq N \leq 500$ .

Output Specification

For each query, output a single integer on its own line which is the distance between the two classrooms in the query.

Sample Input

Copy

Sample Output

Copy

Comments

4

Roronoa_Zoro1540 commented on Jan. 29, 2018, 12:02 a.m.

are hallways bidirectional?

-66

Kirito commented on June 8, 2017, 5:15 p.m.

Because $\mathcal O(N^2)$ $O (N^{2})$ preprocessing passes, the problem has been lowered to 7 points.

This comment is hidden due to too much negative feedback. Show it anyway.

3

imaxblue commented on June 11, 2017, 1:19 a.m.

was that not an intended solution?

or did they just not want data to be huge?

-11

Kirito commented on June 11, 2017, 1:27 a.m.

Likely the latter, as their solution was $\mathcal O(N + Q)$ $O (N + Q)$

This comment is hidden due to too much negative feedback. Show it anyway.

9

root commented on June 9, 2017, 12:33 a.m.

Seriously? I was halfway through solving this problem when you lowered the points. If anything, just tighten the time limit if you think it is too easy.

-4

P234rex commented on June 11, 2017, 3:03 a.m.

That's up to the problemsetter as the admins would be encroaching on their "creative license" by changing the time limit.