結果
問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
ユーザー |
|
提出日時 | 2021-11-17 11:58:45 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 4,074 bytes |
コンパイル時間 | 15,487 ms |
コンパイル使用メモリ | 380,920 KB |
実行使用メモリ | 15,360 KB |
最終ジャッジ日時 | 2024-12-23 08:46:47 |
合計ジャッジ時間 | 23,721 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
use std::io::{Write, BufWriter};// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8macro_rules! input {($($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, usize1) => (read_value!($next, usize) - 1);($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}// Quick-Find data structure.// Verified by: https://atcoder.jp/contests/cf17-tournament-round3-open/submissions/22928265// Verified by: https://atcoder.jp/contests/ttpc2019/submissions/23384553 (polymorphic version)struct QuickFind<T = ()> {root: Vec<usize>, mem: Vec<Vec<usize>>,dat: Vec<T>, default: T,}impl QuickFind<()> {#[allow(unused)]fn new(n: usize) -> Self {Self::with_dat(n, ())}#[allow(unused)]fn unite(&mut self, x: usize, y: usize) {self.unite_with_hooks(x, y, |&(), _| (), |(), ()| ());}}impl<T: Clone> QuickFind<T> {fn with_dat(n: usize, def: T) -> Self {let root = (0..n).collect();let mut mem = vec![vec![]; n];for i in 0..n {mem[i] = vec![i];}QuickFind { root: root, mem: mem, dat: vec![def.clone(); n], default: def }}fn root(&self, x: usize) -> usize {self.root[x]}#[allow(unused)]fn set(&mut self, idx: usize, val: T) {let r = self.root[idx];self.dat[r] = val;}// unite always merges y to x if |x| >= |y|.fn unite_with_hooks<F: FnMut(&T, i64), G: FnMut(T, T) -> T>(&mut self, x: usize, y: usize,mut hook: F, mut merge: G) {let mut x = self.root(x);let mut y = self.root(y);if x == y { return }if self.mem[x].len() < self.mem[y].len() {std::mem::swap(&mut x, &mut y);}let memy = std::mem::replace(&mut self.mem[y], vec![]);for &v in &memy {self.root[v] = x;}self.mem[x].extend_from_slice(&memy);// hookhook(&self.dat[x], -1);hook(&self.dat[y], -1);self.dat[x] = merge(std::mem::replace(&mut self.dat[x], self.default.clone()),std::mem::replace(&mut self.dat[y], self.default.clone()),);hook(&self.dat[x], 1);}#[allow(unused)]fn is_same_set(&self, x: usize, y: usize) -> bool {self.root(x) == self.root(y)}#[allow(unused)]fn size(&self, x: usize) -> usize {let x = self.root(x);self.mem[x].len()}}fn main() {let out = std::io::stdout();let mut out = BufWriter::new(out.lock());macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););}input! {n: usize,a: [f64; n],b: [f64; n],p: [f64; n],q: usize,xy:[(usize1, usize1); q],}let mut qf = QuickFind::with_dat(n, (0.0, 0.0, 0.0));let mut tot = 0.0;for i in 0..n {qf.set(i, (a[i], b[i], 1.0 / p[i]));tot += (a[i] - b[i]) * (a[i] - b[i]) * p[i];}for &(x, y) in &xy {qf.unite_with_hooks(x, y, |(a, b, pinv), dir| {tot += (a - b) * (a - b) / pinv * dir as f64;}, |(a1, b1, pinv1), (a2, b2, pinv2)| (a1 + a2, b1 + b2, pinv1 + pinv2));puts!("{}\n", tot);}}