結果
| 問題 | No.2909 Imaginary Summer |
| ユーザー |
 ArcAki
|
| 提出日時 | 2024-09-27 08:33:17 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,903 bytes |
| コンパイル時間 | 13,663 ms |
| コンパイル使用メモリ | 389,644 KB |
| 実行使用メモリ | 33,476 KB |
| 最終ジャッジ日時 | 2024-10-02 17:32:56 |
| 合計ジャッジ時間 | 26,524 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 TLE * 1 -- * 24 |
ソースコード
#[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")};}#[derive(Debug, PartialEq, PartialOrd)]struct OrderedFloat(f64);impl Eq for OrderedFloat {}impl Ord for OrderedFloat {fn cmp(&self, other: &Self) -> Ordering{self.partial_cmp(&other).unwrap()}}const INF: i64 = 1<<60;#[derive(Debug)]struct QuadTree{tree: Vec<Node>,}#[derive(Debug, Copy, Clone)]struct Node{t: usize,point: (i64, i64),mix: i64,mxx: i64,miy: i64,mxy: i64,leaf: usize,}impl QuadTree {fn new(mix: i64, mxx: i64, miy: i64, mxy: i64)->Self{let root = Node{t: 0, point: (INF, INF), mix, mxx, miy, mxy, leaf: 0};QuadTree{tree: vec![root]}}fn insert(&mut self, pointer: usize, p: i64, q: i64){let mut node = self.tree[pointer];let t = node.t;match t{0 => {self.tree[pointer].point = (p, q);self.tree[pointer].t = 1;},1 => {self.tree[pointer].t = 2;let (px, py) = node.point;node.t = 2;self.divide(pointer, &mut node);let nex1 = self.down(px, py, &node).unwrap();self.insert(nex1, px, py);let nex2 = self.down(p, q, &node).unwrap();self.insert(nex2, p, q);},_ => {let nex = self.down(p, q, &node).unwrap();self.insert(nex, p, q);}}}fn down(&mut self, p: i64, q: i64, node: &Node)->Option<usize>{if node.t < 2{return None;}let mut nex = node.leaf;let (mx, my) = ((node.mxx+node.mix)/2, (node.mxy+node.miy)/2);if p >= mx {nex += 1;}if q >= my {nex += 2;}Some(nex)}fn divide(&mut self, pointer: usize, node: &mut Node){let nex = self.tree.len();let (mx, my) = ((node.mxx+node.mix)/2, (node.mxy+node.miy)/2);self.tree[pointer].leaf = nex;node.leaf = nex;self.tree.push(Node{t: 0, point: (INF, INF), mix: node.mix, mxx: mx, miy: node.miy, mxy: my, leaf: 0});self.tree.push(Node{t: 0, point: (INF, INF), mix: mx, mxx: node.mxx, miy: node.miy, mxy: my, leaf: 0});self.tree.push(Node{t: 0, point: (INF, INF), mix: node.mix, mxx: mx, miy: my, mxy: node.mxy, leaf: 0});self.tree.push(Node{t: 0, point: (INF, INF), mix: mx, mxx: node.mxx, miy: my, mxy: node.mxy, leaf: 0});}fn query(&mut self, pointer: usize, p: i64, q: i64, res: &mut ((i64, i64), i64)){let node = self.tree[pointer];if node.t == 2{let leaf = node.leaf;for i in 0..4{let nex = self.tree[leaf+i];if possible_dist(p, q, &nex) < res.1{self.query(leaf+i, p, q, res);}}} else if node.t == 1{let (x, y) = node.point;let d = (p-x)*(p-x)+(q-y)*(q-y);if d < res.1{*res = ((x, y), d);}}}}fn dist_calc(p: &(i64, i64), q: &(i64, i64))->f64{let (x1, y1) = p;let (x2, y2) = q;(((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) as f64).sqrt()}fn possible_dist(p: i64, q: i64, node: &Node)->i64{let (mix, mxx, miy, mxy) = (node.mix, node.mxx, node.miy, node.mxy);let f1 = mix <= p && p <= mxx;let f2 = miy <= q && q <= mxy;if f1 && f2{return 0;} else if f1{return (miy-q).abs().min((q-mxy).abs())} else if f2{return (mix-p).abs().min((mxx-p).abs())}let x = (miy-q).abs().min((q-mxy).abs());let y = (mix-p).abs().min((mxx-p).abs());return x*x+y*y}fn main() {input!{n: usize, m: usize, k: usize,p: (i64, i64),s: [(i64, i64); n],t: [(i64, i64); k],v: f64,e: [(usize1, usize1); m],}let p = (p.0, p.1);let mut edge = vec![Vec::new(); n];for &(u, v) in &e{edge[u].push(v);edge[v].push(u);}let mut dic = HashMap::new();for i in 0..n{dic.insert((s[i].0, s[i].1), i);}let mut quadtree = QuadTree::new(-100000, 100001, -100000, 100001);for &(u, v) in &s{quadtree.insert(0, u, v);}let mut hotel = ((0, 0), INF);quadtree.query(0, p.0, p.1, &mut hotel);let ss = dic[&(hotel.0.0, hotel.0.1)];let pre = (hotel.1 as f64).sqrt();let mut time = vec![1e60; n];time[ss] = 0.;let mut used = vec![false; n];let mut heap = BinaryHeap::new();heap.push(Reverse((OrderedFloat(0.), ss)));while let Some(Reverse((OrderedFloat(w), x))) = heap.pop(){if used[x]{continue}used[x] = true;for &nex in &edge[x]{if used[nex]{continue}let dx = dist_calc(&s[nex], &s[x])/v;if time[nex] > w+dx{time[nex] = time[x]+dx;heap.push(Reverse((OrderedFloat(time[nex]), nex)));}}}let mut ans = 0.;for i in 0..k{let mut st = ((0, 0), INF);let (x, y) = t[i];quadtree.query(0, x, y, &mut st);let d1 = dist_calc(&st.0, &t[i]);let t1 = time[dic[&(st.0.0, st.0.1)]];ans += (dist_calc(&p, &t[i]).min(pre+d1+t1))*2.;}println!("{}", ans);}