結果

問題 No.1103 Directed Length Sum
コンテスト
ユーザー akakimidori
提出日時 2020-07-04 09:42:17
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 270 ms / 3,000 ms
コード長 4,648 bytes
コンパイル時間 18,221 ms
コンパイル使用メモリ 383,132 KB
実行使用メモリ 64,868 KB
最終ジャッジ日時 2024-09-17 20:22:16
合計ジャッジ時間 20,396 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin graph ----------
struct Graph<T> {
    size: usize,
    edge: Vec<(usize, usize, T)>,
    graph: Vec<(usize, T)>,
    start: Vec<usize>,
    length: Vec<usize>,
    ini: T,
}

#[allow(dead_code)]
impl<T: Clone> Graph<T> {
    fn new(size: usize, ini: T) -> Self {
        Graph {
            size: size,
            edge: vec![],
            graph: Vec::with_capacity(size),
            start: Vec::with_capacity(size),
            length: Vec::with_capacity(size),
            ini: ini,
        }
    }
    fn add_edge(&mut self, src: usize, dst: usize, val: T) {
        assert!(src < self.size && dst < self.size);
        self.edge.push((src, dst, val));
    }
    fn build(&mut self) {
        let size = self.size;
        self.length.clear();
        self.length.resize(size, 0);
        for e in self.edge.iter() {
            self.length[e.0] += 1;
        }
        self.start.clear();
        let mut sum = 0;
        for d in self.length.iter() {
            sum += *d;
            self.start.push(sum);
        }
        assert!(self.edge.len() == sum);
        self.graph.clear();
        self.graph.resize(self.edge.len(), (size, self.ini.clone()));
        while let Some((src, dst, val)) = self.edge.pop() {
            self.start[src] -= 1;
            let k = self.start[src];
            self.graph[k] = (dst, val);
        }
        assert!(self
            .start
            .windows(2)
            .zip(self.length.iter())
            .all(|(s, l)| s[1] - s[0] == *l));
        assert!(*self.start.last().unwrap() + *self.length.last().unwrap() == self.graph.len());
        //        }
    }
    // remove と銘打っているが実際に要素は削除されないので注意
    fn remove(&mut self, v: usize, k: usize) {
        assert!(v < self.size && k < self.length[v]);
        let s = self.start[v];
        let len = self.length[v];
        self.graph.swap(s + k, s + len - 1);
        self.length[v] -= 1;
    }
}

impl<T> std::ops::Index<usize> for Graph<T> {
    type Output = [(usize, T)];
    fn index(&self, v: usize) -> &Self::Output {
        let len = self.length[v];
        let s = self.start[v];
        &self.graph[s..(s + len)]
    }
}

impl<T> std::ops::IndexMut<usize> for Graph<T> {
    fn index_mut(&mut self, v: usize) -> &mut Self::Output {
        let len = self.length[v];
        let s = self.start[v];
        &mut self.graph[s..(s + len)]
    }
}
// ---------- end graph ----------
// ---------- begin Scanner(require delimiter) ----------
mod scanner {
    pub struct Scanner<R> {
        reader: R,
        buf: Vec<u8>,
    }
    #[allow(dead_code)]
    impl<R: std::io::BufRead> Scanner<R> {
        pub fn new(reader: R) -> Self {
            Scanner {
                reader: reader,
                buf: Vec::with_capacity(1024),
            }
        }
        fn read(&mut self, del: u8) {
            self.buf.clear();
            self.reader.read_until(del, &mut self.buf).ok();
            assert!(self.buf.pop().unwrap() == del);
        }
        pub fn next<T: std::str::FromStr>(&mut self, del: u8) -> T {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .parse::<T>()
                .ok()
                .unwrap()
        }
        pub fn next_bytes(&mut self, del: u8) -> Vec<u8> {
            self.read(del);
            std::str::from_utf8(&self.buf)
                .unwrap()
                .trim()
                .bytes()
                .collect()
        }
    }
}
// ---------- end scanner(require delimiter) ----------

fn main() {
    let stdin = std::io::stdin();
    let mut sc = scanner::Scanner::new(stdin.lock());
    run(&mut sc);
}

fn run<R: std::io::BufRead>(sc: &mut scanner::Scanner<R>) {
    let n: usize = sc.next(b'\n');
    let mut g = Graph::new(n, ());
    let mut child = vec![false; n];
    for _ in 1..n {
        let a: usize = sc.next(b' ');
        let b: usize = sc.next(b'\n');
        g.add_edge(a - 1, b - 1, ());
        child[b - 1] = true;
    }
    g.build();
    let root = child.into_iter().position(|p| !p).unwrap();
    let mut q = vec![root];
    for i in 0..n {
        let v = q[i];
        for &(u, _) in g[v].iter() {
            q.push(u);
        }
    }
    let mut ans = 0u64;
    let mut dp = vec![(0, 0); n];
    for &v in q.iter().rev() {
        let mut val = (0u64, 1u64);
        for &(u, _) in g[v].iter() {
            let p = &dp[u];
            val.0 += p.0 + p.1;
            val.1 += p.1;
        }
        ans += val.0;
        dp[v] = val;
    }
    println!("{}", ans % 1_000_000_007);
}
0