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

eastwest Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

eastwest.html

Olimpiada Informatyczna
XI Olimpiad in Informatics 2003/2004

Task: WSC

East-West

III stage competition  
Source file: wsc.*
Memory limit: 256 MB

International agreements signed by the Awfully Vast State impose on it transit obligations - it has to enable the transport of nuclear waste from its eastern neighbours power plants to recycling facilities in the West, by means of its railway system. Ecological reasons impose such traffic organization, that the waste-carrying trains leave the territory of the state as quickly as possible.
The railway network in this country has a very peculiar structure. It consists of n cities - railway junctions and n-1 two-way railway track segments, connecting the junctions. Transport is possible between each pair of cities. Furthermore, there is a section of the railway track, whose ends are not border cities and every connection from the eastern to the western border has to lead through that very section.
All waste-carrying trains arrive at the eastern border on the same day, before dawn, at distinct checkpoints, however. For safety reasons the trains only move during the day. Only a single waste-carrying train can move on a given track section at a time, but an unlimited amount of them can wait at a junction. It takes one day for a train to traverse a section of the track. The traffic has to be organized in such a way, that allows each waste-carrying train to reach a distinct destination on the western border.
How many days, at least, do the waste-carrying trains have to spend on the territory of the Awfully Vast State?

Task

Your task is to write a programme which:

  • reads from the standard input a description of the railway network and border checkpoints at which the waste-carrying trains have arrived,
  • finds the minimal number of days the transit has to last,
  • writes the solution to the standard output.

Input

The first line of the input contains three integers 1 < n, w, z < 106, n >= w+z+2, separated by single spaces. n denotes the number of junctions (which are labelled with 1,...,n), while w and z denote the number of border checkpoints on the eastern and western border, respectively. The checkpoints on the eastern border are labelled with 1,...,w, while those on the western border with n-z+1,...,n.
In the following n-1 lines there is a decription of the railway network. Each line contains two distinct integers, 1 < a,b < n, separated by a single space. They denote junctions connected by a section of the railway.
The n+1st line contains a single integer p, 1 < p < w, 1 < p < z, denoting the number of waste-carrying trains. In the next (and last) line of the input there are p distinct integers, all of which are not greater than w, separated by single spaces. These are the numbers of checkpoints on the eastern border, at which the waste-carrying trains have arrived.

Output

The first and only line of the output should contain exactly one integer, denoting the minimal amount of days the waste have to spend on the territory of the state.

Example

For the input data:
9 2 3
1 3
2 3
4 3
4 5
4 6
7 4
5 8
9 6
2
1 2
the correct outcome is:
4

The arrows denote the movement of the trains in consecutive days for one of the optimal organizations of the railway traffic - a loop means that on a given day the train waited at the junction.

wsczad.png

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100173s256MBAverage

Judge Compile Command

g++-8 ans.cpp -o eastwest -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.