結果

問題 No.1103 Directed Length Sum
ユーザー akakimidoriakakimidori
提出日時 2020-07-04 09:42:17
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 145 ms
64,868 KB
testcase_03 AC 133 ms
64,744 KB
testcase_04 AC 127 ms
37,552 KB
testcase_05 AC 270 ms
63,216 KB
testcase_06 AC 81 ms
24,988 KB
testcase_07 AC 18 ms
7,552 KB
testcase_08 AC 29 ms
10,368 KB
testcase_09 AC 12 ms
5,504 KB
testcase_10 AC 41 ms
13,664 KB
testcase_11 AC 165 ms
40,816 KB
testcase_12 AC 88 ms
25,272 KB
testcase_13 AC 41 ms
13,952 KB
testcase_14 AC 9 ms
5,376 KB
testcase_15 AC 64 ms
20,156 KB
testcase_16 AC 165 ms
45,456 KB
testcase_17 AC 169 ms
47,384 KB
testcase_18 AC 39 ms
13,568 KB
testcase_19 AC 165 ms
41,792 KB
testcase_20 AC 15 ms
6,272 KB
testcase_21 AC 26 ms
9,600 KB
testcase_22 AC 121 ms
34,216 KB
testcase_23 AC 71 ms
21,528 KB
権限があれば一括ダウンロードができます

ソースコード

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