No.2909 Imaginary Summer
※Note※ Languages with speeds around that of PyPy3 may not finish within the execution time limit. Fast languages such as C++ are recommended.
Problem Statement
Shiro is going on a trip to a certain region to visit $K$ destinations. This region lies on a coordinate plane, and a railway consisting of $N$ stations runs through it. He travels between the destinations and the hotel by railway and on foot.
He may also go directly on foot.
The railway network is connected and has $M$ lines, where line $i$ connects station $S_i$ and station $T_i$ bidirectionally along a straight line.
The hotel is at point $(P, Q)$, station $j$ is built at point $(X_j, Y_j)$, and destination $k$ is at point $(A_k, B_k)$.
On this trip, he repeats the following $K$ times: leave the hotel, choose one destination he has not chosen yet and visit it, have a meal, and return to the hotel.
Shiro is a light eater, so even if there are other unvisited destinations along his route, he cannot eat there, and he must return to the hotel once before visiting them.
Shiro's walking speed is 1, and his travel speed by railway is V = $10^{18}$.
Distances are defined as Euclidean distances, and the time for connections and transfers need not be considered.
Find the minimum possible total travel time of this trip.
For inputs other than the samples, the coordinates are generated uniformly at random and the lines are generated randomly. For details on the input, see the input description below.
Input
$N\ M\ K$ $P\ Q$ $X_1\ Y_1$ $:$ $X_N\ Y_N$ $A_1\ B_1$ $:$ $A_K\ B_K$ V $S_1\ T_1$ $:$ $S_M\ T_M$
All input values are integers and satisfy the following conditions. Inputs other than the samples are generated by the algorithm below so as to satisfy these conditions.
・$ 2 ≤ N ≤ 10^5$
・$ N-1 ≤ M ≤ \min(\frac{N × (N-1)}{2}, 10^5)$
・$ 1 ≤ K ≤ 10^5$
・$ -10^5 ≤ P, Q ≤ 10^5$
・$ -10^5 ≤ X_i, Y_i ≤ 10^5$
・$ (X_i, Y_i) ≠ (X_j, Y_j)\ (i ≠ j)$
・$ -10^5 ≤ A_i, B_i ≤ 10^5 $
・$ (A_i, B_i) ≠ (A_j, B_j)\ (i ≠ j)$
・$ (P, Q) ≠ (X_i, Y_i)$
・$ (P, Q) ≠ (A_i, B_i)$
・$ (X_i, Y_i) ≠ (A_j, B_j)$
・V $=10^{18}$
・$ 1 ≤ S_i, T_i ≤ N$
・$ S_i ≠ T_i $
・$ \{S_i, T_i\} ≠ \{S_j, T_j\}\ (i ≠ j)$
・The railway network is connected.
The input is generated as follows.
- First, the seed of the random number generator $R$, which is used throughout, is specified using another random number generator $R'$ with an arbitrarily chosen seed. All random numbers and shuffles other than those for determining $N, M, K$ use this generator $R$.
- $N, M, K$ satisfying the conditions are specified either directly or by random numbers from the generator $R'$.
- Next, using the generator $R$, the values of the hotel's coordinates $P, Q$ are each determined uniformly at random from the values between $-10^5$ and $10^5$, inclusive.
- For the station coordinates, in the order $j = 1, 2, …, N$, a candidate coordinate $(x, y)$ is repeatedly generated in the same way as above until it is a coordinate not yet used as a hotel or station coordinate in the generation so far, and the final value of $(x, y)$ becomes the coordinate $(X_j,\ Y_j)$ of station $j$.
- Likewise, for the destination coordinates, in the order $k = 1, 2, …, K$, generation is repeated until the value is not yet used as a hotel, station, or destination coordinate, and it becomes the coordinate $(A_k,\ B_k)$ of destination $k$.
- Set V = $10^{18}$.
- Generate $M$ lines by the following procedure.
- First, define an empty array $A$ and an array $B$ holding 1 copy of each value between $1$ and $N$, inclusive.
- Next, shuffle $B$ so that it is uniformly random as a whole.
- Remove the last element of $B$ and store its value in $A$.
- Then, for $i = 1, 2, …, N-1$, choose one element of $A$ uniformly at random as $a$, let $b$ be the last element of $B$, set $(S_i, T_i) = (a, b)$, remove $b$ from the array $B$, and add $b$ to the array $A$.
- The remaining $M-N+1$ lines are determined by repeating the following: for 2 integers $u, v$ chosen uniformly at random from the values between $1$ and $N$, inclusive, if $u≠v$ and there is no line connecting station $u$ and station $v$ yet, add it as a new line, and if it is the $i$-th line, set $(S_i, T_i) = (u, v)$.
The seed values for the input test cases are published on the editorial page. The base of the program code actually used for generation is given below.
(In practice, only the operations described in the comments were added.)
Input generator code baseline (Rust)
#[allow(unused_imports)]
use std::{collections::{HashSet, HashMap, BTreeSet, BTreeMap, BinaryHeap, VecDeque}, cmp::{Reverse, PartialOrd, Ordering, max, min}, mem::swap};
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<\Vec<\_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<\Vec<\char>>()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
struct XorShiftStar{
state: u64,
}
impl XorShiftStar{
fn new(seed: u64)->Self{
XorShiftStar{state: seed}
}
fn next(&mut self)->u64{
let mut x = self.state;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.state = x;
x.wrapping_mul(0x2545F4914F6CDD1D)
}
fn get(&mut self, l: usize, r: usize) -> usize {
let range = r - l + 1;
let num = (self.next() as usize) % (range) + l;
num
}
fn shuffle<T>(&mut self, a: &mut Vec<T>){
let n = a.len();
for i in 0..n{
let j = self.get(0, i);
a.swap(i, j);
}
}
fn choose<T>(&mut self, a: &Vec<T>)->T where T: Copy{
let n = a.len();
let p = self.get(0, n-1);
a[p]
}
}
fn main(){
input!{
c: u64,
}
//入力ごとに乱数シードを変更するため調整する
let config1 = 0;
let config2 = 0;
//ここまで
let mut pre_rng = XorShiftStar::new(config1*c+config2);
for _ in 0..c{
pre_rng.next();
}
let seed = (pre_rng.get(0, 199999) as u64+c*config2)%200000;
let mut rng = XorShiftStar::new(seed);
//ここは直接指定して操作するかpre_rngにより決定
let n = pre_rng.get(2, 2);
let m = pre_rng.get(n-1, 100000).min(n*(n-1)/2);
let k = pre_rng.get(1, 100000);
//ここまで。ここ以降は完全にrngのみで乱数を扱う。
let mx = 200000i32;
let h = 100000i32;
let mut p = Vec::new();
p.push(rng.get(0, mx as usize) as i32-h);
p.push(rng.get(0, mx as usize) as i32-h);
let mut used1 = HashSet::new();
used1.insert((p[0], p[1]));
let mut cnt = 0;
let mut station = Vec::new();
while cnt < n{
let (u, v) = (rng.get(0, mx as usize) as i32-h, rng.get(0, mx as usize) as i32-h);
if used1.contains(&(u, v)){continue}
cnt += 1;
used1.insert((u, v));
station.push((u, v));
}
let mut t = Vec::new();
cnt = 0;
while cnt < k{
let (u, v) = (rng.get(0, mx as usize) as i32-h, rng.get(0, mx as usize) as i32-h);
if used1.contains(&(u, v)){continue}
cnt += 1;
used1.insert((u, v));
t.push((u, v));
}
let z = 1_000_000_000_000_000_000i64;
let mut leaf = Vec::new();
for i in 0..n{
leaf.push(i);
}
rng.shuffle(&mut leaf);
let mut parent = Vec::new();
let x = leaf.pop().unwrap();
parent.push(x);
let mut e = Vec::new();
let mut used2 = HashSet::new();
for _ in 1..n{
let pre = rng.choose(&parent);
let nex = leaf.pop().unwrap();
e.push((pre, nex));
parent.push(nex);
used2.insert((pre, nex));
used2.insert((nex, pre));
}
let mut cnt = n-1;
while cnt < m{
let (u, v) = (rng.get(0, n-1), rng.get(0, n-1));
if u==v||used2.contains(&(u, v)){continue}
used2.insert((u, v));
used2.insert((v, u));
e.push((u, v));
cnt += 1;
}
assert!(n >= 2);
assert!(n <= 100000);
assert!(n-1 <= m);
assert!(m <= n*(n-1)/2);
assert!(m <= 100000);
assert!(k >= 1);
assert!(k <= 100000);
assert!(p[0] <= h);
assert!(p[0] >= -h);
assert!(p[1] <= h);
assert!(p[1] >= -h);
assert_eq!(z, 1_000_000_000_000_000_000);
println!("{} {} {}", n, m, k);
println!("{} {}", p[0], p[1]);
for &(u, v) in &station{
assert!(u <= h);
assert!(u >= -h);
assert!(v <= h);
assert!(v >= -h);
println!("{} {}", u, v);
}
for &(u, v) in &t{
assert!(u <= h);
assert!(u >= -h);
assert!(v <= h);
assert!(v >= -h);
println!("{} {}", u, v);
}
println!("{}", z);
for &(u, v) in &e{
assert!(u+1 >= 1);
assert!(v+1 >= 1);
assert!(u+1 <= n);
assert!(v+1 <= n);
println!("{} {}", u+1, v+1);
}
//ケース名はケースごとに直接指定するか渡された値を利用。シード値は出力から確認している。その後テストケース名から削除している。
eprintln!("00_some_{}_seed_{}", c, seed);
}
Output
Output the answer. Your answer is considered correct if its absolute or relative error from the value of the writer's solution is at most $10^{-5}$.
Print a newline at the end.
Sample
Sample 1
Input
5 4 6 12 3 2 3 5 1 6 5 9 7 4 10 14 5 2 12 1 2 4 6 7 9 7 -2 1000000000000000000 1 2 3 2 5 3 3 4
Output
78.3769065542748
In the image above, the stations and lines are shown as a graph, the hotel as a green star, and the destinations as crosses.
For example, to go to destination 1, going there and back directly without using the railway takes $4 \sqrt{2}$. As shown here, there are cases where the railway is not used.
Note that coordinates may be negative.
Sample 2
Input
2 1 1 -100000 -100000 -100000 -99999 -100000 -99998 100000 100000 1000000000000000000 1 2
Output
565684.5965291844
If taking the railway shortens the time even slightly, that option takes priority.
Sample 3
Input
12 24 17 49568 69196 -98957 -87293 96282 -5498 30527 -30128 21828 -29401 -37956 94439 -78187 -73404 -25005 -38011 86936 40205 -8187 -34299 48841 96226 -29661 53258 -10550 -2726 38374 20431 -72654 -13277 -88480 -1097 44653 55980 13844 -15041 -57186 -70519 47119 -20186 -65670 18338 26320 -53469 -51293 14935 22716 86271 73126 -69136 30758 96068 -91332 -31362 3606 35963 -29619 -25760 -28544 55494 1000000000000000000 3 9 9 7 9 2 2 8 3 1 1 11 3 6 6 12 8 4 11 10 4 5 2 4 8 11 9 12 2 7 11 7 12 8 1 6 10 4 8 9 2 6 5 2 10 5 1 9
Output
1857858.1089122023
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。