結果
問題 | No.922 東北きりきざむたん |
ユーザー |
![]() |
提出日時 | 2019-11-08 23:07:29 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,543 bytes |
コンパイル時間 | 18,406 ms |
コンパイル使用メモリ | 377,112 KB |
実行使用メモリ | 130,688 KB |
最終ジャッジ日時 | 2024-09-15 02:16:16 |
合計ジャッジ時間 | 21,969 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 115 ms
49,024 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 110 ms
52,736 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 378 ms
115,140 KB |
testcase_26 | AC | 374 ms
114,492 KB |
testcase_27 | AC | 364 ms
114,752 KB |
testcase_28 | AC | 160 ms
70,528 KB |
testcase_29 | AC | 396 ms
130,688 KB |
コンパイルメッセージ
warning: type `euler_tour` should have an upper camel case name --> src/main.rs:114:8 | 114 | struct euler_tour { | ^^^^^^^^^^ help: convert the identifier to upper camel case: `EulerTour` | = note: `#[warn(non_camel_case_types)]` on by default warning: type `sparse_table` should have an upper camel case name --> src/main.rs:160:8 | 160 | struct sparse_table { | ^^^^^^^^^^^^ help: convert the identifier to upper camel case: `SparseTable`
ソースコード
#![allow(unused_imports)] #![allow(non_snake_case, unused)] use std::cmp::*; use std::collections::*; use std::ops::*; macro_rules! eprint { ($($t:tt)*) => {{ use ::std::io::Write; let _ = write!(::std::io::stderr(), $($t)*); }}; } macro_rules! eprintln { () => { eprintln!(""); }; ($($t:tt)*) => {{ use ::std::io::Write; let _ = writeln!(::std::io::stderr(), $($t)*); }}; } macro_rules! dbg { ($v:expr) => {{ let val = $v; eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val); val }} } macro_rules! mat { ($($e:expr),*) => { Vec::from(vec![$($e),*]) }; ($($e:expr,)*) => { Vec::from(vec![$($e),*]) }; ($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) }; ($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) }; } macro_rules! ok { ($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => { $a$([$i])*.$f($($t),*) }; ($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { { let t = $e; ok!($a$([$i])*.$f($($es),*)$(@$t)*@t) } }; } pub fn readln() -> String { let mut line = String::new(); ::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e)); line } macro_rules! read { ($($t:tt),*; $n:expr) => {{ let stdin = ::std::io::stdin(); let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| { let line = line.unwrap(); let mut it = line.split_whitespace(); _read!(it; $($t),*) }).collect::<Vec<_>>(); ret }}; ($($t:tt),*) => {{ let line = readln(); let mut it = line.split_whitespace(); _read!(it; $($t),*) }}; } macro_rules! _read { ($it:ident; [char]) => { _read!($it; String).chars().collect::<Vec<_>>() }; ($it:ident; [u8]) => { Vec::from(_read!($it; String).into_bytes()) }; ($it:ident; usize1) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1 }; ($it:ident; [usize1]) => { $it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>() }; ($it:ident; [$t:ty]) => { $it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>() }; ($it:ident; $t:ty) => { $it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e)) }; ($it:ident; $($t:tt),+) => { ($(_read!($it; $t)),*) }; } pub fn main() { let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join(); } const MOD: u32 = 1_000_000_007; #[derive(Copy,Clone)] struct Pair<T,U> { x: T, y: U, } impl<T,U> Pair<T,U> { fn new(x: T, y: U) -> Pair<T,U> { Pair { x: x, y: y, } } } struct euler_tour { G: Vec<Vec<Pair<usize,i64>>>, tour: Vec<usize>, L: Vec<usize>, R: Vec<usize>, depth: Vec<usize>, weight: Vec<i64>, n: usize, } impl euler_tour{ fn new(n: usize) -> euler_tour { euler_tour{ G: vec![vec![];n], tour: vec![], L: vec![0;n], R: vec![0;n], depth: vec![0;n], weight: vec![0;n], n: n, } } fn add_edge(&mut self, s: usize, t: usize, w: i64){ self.G[s].push(Pair::new(t,w)); self.G[t].push(Pair::new(s,w)); } fn init(&mut self, root: usize) { self.dfs(root, self.n, 0, 0); } fn dfs(&mut self, v: usize, p: usize, d: usize, w: i64){ self.tour.push(v); self.L[v] = self.tour.len()-1; self.depth[v] = d; self.weight[v] = w; for z in self.G[v].clone() { if z.x == p {continue;} self.dfs(z.x, v, d+1, w+z.y); self.tour.push(v); } self.R[v] = self.tour.len()-1; } } struct sparse_table { log_t: Vec<usize>, table: Vec<Vec<Pair<usize,usize>>>, n: usize, } impl sparse_table { fn new() -> sparse_table{ sparse_table{ log_t: vec![], table: vec![vec![]], n: 0, } } // Pair<s,t> // s: 値(最小値の検索の対象となる) // t: インデックス(任意の値) fn init(&mut self, arr: Vec<Pair<usize,usize>>) { let n = arr.len(); let mut lt: Vec<usize> = vec![0;n+1]; for i in 2..n+1 { lt[i] = lt[i >> 1] + 1; } let sz = lt[n]; self.log_t = lt; self.table = vec![vec![Pair::new(usize::max_value(),0);sz+1];n]; self.n = n; for i in 0..n { self.table[i][0] = arr[i]; } for k in 1..n { if (1 << k) > n {break;} for i in 0..n { if i + (1 << k) > n {break;} self.table[i][k] = { let a = self.table[i][k - 1]; let b = self.table[i + (1 << (k - 1))][k - 1]; if a.x <= b.x {a} else {b} }; } } } // [s,t]の最小値を返す fn query(&mut self, s: usize, t: usize) -> Pair<usize,usize> { let k = self.log_t[t-s+1]; let a = self.table[s][k]; let b = self.table[t + 1 - (1 << k)][k]; if a.x <= b.x {a} else {b} } } struct LCA{ euler: euler_tour, st: sparse_table, n: usize, } impl LCA{ fn new(n: usize) -> LCA { LCA{ euler: euler_tour::new(n), st: sparse_table::new(), n: n, } } fn add_edge(&mut self, s: usize, t: usize, w: i64){ self.euler.add_edge(s,t,w); } // euler tourの構築 // sparce tableの構築 fn init(&mut self) { self.euler.init(0); let sz = self.euler.tour.len(); let mut arr: Vec<Pair<usize,usize>> = vec![Pair::new(0,0);sz]; for i in 0..sz { arr[i] = Pair::new(self.euler.depth[self.euler.tour[i]], self.euler.tour[i]); } self.st.init(arr); } // sとtのLCAを求める fn lca(&mut self, s: usize, t: usize) -> usize { self.st.query(min(self.euler.L[s],self.euler.L[t]), max(self.euler.R[s], self.euler.R[t])).y } } pub struct UnionFind { data: Vec<i32>, } impl UnionFind { /// Creates a object with n disjoint sets. `i`-th set is `{ i }`. pub fn new(n: usize) -> UnionFind { UnionFind { data: vec![-1; n] } } /// Unite a set including `x` and another set including y into one. /// Returns `true` only if they were in different set. pub fn unite(&mut self, x: usize, y: usize) -> bool { let x = self.root(x); let y = self.root(y); if x != y { let (x, y) = if self.data[x] <= self.data[y] { (x, y) } else { (y, x) }; self.data[x] += self.data[y]; self.data[y] = x as i32; } x != y } /// Returns `true` only if `x` and `y` are in a same set. pub fn same(&mut self, x: usize, y: usize) -> bool { self.root(x) == self.root(y) } /// Returns the number of elements of a set including `x`. pub fn size(&mut self, x: usize) -> u32 { let r = self.root(x); (-self.data[r]) as u32 } /// internal method to return representative element of a set including `x`. pub fn root(&mut self, x: usize) -> usize { if self.data[x] < 0 { x } else { let nx = self.data[x] as usize; let r = self.root(nx); self.data[x] = r as i32; r } } } fn construct_tree (cur: usize, p: usize, graph: &Vec<Vec<usize>>, count: &[usize], node: &mut Vec<Vec<(usize,usize)>>) -> usize{ let mut val = vec![]; let mut ret = count[cur]; for g in &graph[cur] { if *g==p {continue;} let sum = construct_tree(*g, cur, graph, count, node); val.push((*g,sum)); ret += sum; } node[cur] = val; ret } fn find_node (cur: usize, p: usize, count: &[usize], node: &Vec<Vec<(usize, usize)>>, z: usize) -> usize { let mut sum = count[cur]; for x in &node[cur] { sum += x.1; } let mut score = 0; let mut target = cur; let mut t2 = 0; for x in &node[cur] { // println!("cur {} v {} val {} sum {}", cur, x.0, x.1, sum); let v = x.0; let val = x.1; if v==p {continue;} let tmp = val as i64 - (sum as i64 - val as i64) - z as i64; // println!("{}", tmp); if tmp > score { score = tmp; target = v; t2 = val; } } // println!("target {} cur {}", target); if target==cur { return cur; } find_node(target, cur, count, node, sum-t2) // return 0; } fn solve() { let (n,m,q) = read!(usize, usize, usize); let edge = read!([usize];m); let query = read!([usize];q); let mut uf = UnionFind::new(n); let mut graph = vec![vec![];n]; for e in &edge { let s = e[0]-1; let t = e[1]-1; graph[s].push(t); graph[t].push(s); uf.unite(s,t); } let mut num = 0; let mut seen = vec![false; n]; let mut rv = vec![]; let mut id = vec![0; n]; for i in 0..n { let root = uf.root(i); if !seen[root] { num+=1; rv.push((root,num-1)); id[root] = num-1; } seen[root] = true; } let mut lca = vec![]; for i in &rv { lca.push(LCA::new(uf.size(i.0) as usize)); } let mut idx = vec![0; n]; let mut tx = vec![0;n]; for i in 0..n { let root = uf.root(i); tx[i] = idx[root]; idx[root] += 1; } for e in &edge { let s = e[0]-1; let t = e[1]-1; let root = uf.root(s); lca[id[root]].add_edge(tx[s],tx[t],1); } for i in 0..num { lca[i].init(); } let mut ans = 0; let mut count = vec![0; n]; for i in 0..q { let s = query[i][0]-1; let t = query[i][1]-1; if uf.same(s,t) { let root = uf.root(s); let z = lca[id[root]].lca(tx[s],tx[t]); let dist = lca[id[root]].euler.weight[tx[s]] + lca[id[root]].euler.weight[tx[t]] - 2*lca[id[root]].euler.weight[z]; ans += dist; } else{ count[s] += 1; count[t] += 1; } } let mut node = vec![vec![];n]; let mut tar = vec![0;n]; for i in &rv { let root = i.0; construct_tree(root, n, &graph, &count, &mut node); let target = find_node(root, n, &count, &node, 0); tar[root] = target; // println!("{}", target); } for i in 0..n { let root = uf.root(i); let z = lca[id[root]].lca(tx[i],tx[tar[root]]); let dist = lca[id[root]].euler.weight[tx[i]] + lca[id[root]].euler.weight[tx[tar[root]]] - 2*lca[id[root]].euler.weight[z]; ans += dist * count[i] as i64; // println!("i {} root {} count {} dist {}", i, root, count[i], dist); } println!("{}", ans); } fn run() { solve(); }