結果

問題 No.1365 [Cherry 1st Tune] Whose Fault?
ユーザー koba-e964koba-e964
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_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);
// hook
hook(&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);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0