#396836 (Rust) No.922 東北きりきざむたん

• 問題: No.922 東北きりきざむたん
• ユーザー: ziita
• 提出日時: 2019-11-08 23:07:29
• 言語: Rust (1.83.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

ファイルパターン	結果
sample	AC * 4
other	AC * 11 WA * 15

コンパイルメッセージ

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();
}