Submission #7498006


Source Code Expand

Copy
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let (N, M): (usize, usize) = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap()
        )
    };
    let (a, b): (Vec<usize>, Vec<usize>) = {
        let (mut a, mut b) = (vec![], vec![]);
        for _ in 0..M {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            a.push(iter.next().unwrap().parse().unwrap());
            b.push(iter.next().unwrap().parse().unwrap());
        }
        (a, b)
    };
    let Q: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let (v, d, c): (Vec<usize>, Vec<usize>, Vec<usize>) = {
        let (mut v, mut d, mut c) = (vec![], vec![], vec![]);
        for _ in 0..Q {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            v.push(iter.next().unwrap().parse().unwrap());
            d.push(iter.next().unwrap().parse().unwrap());
            c.push(iter.next().unwrap().parse().unwrap());
        }
        (v, d, c)
    };

    // 最後の操作から順に処理
    // 拡張グラフに対してDFSすることで計算量を抑える
    let G = {
        let mut G = vec![std::collections::HashSet::new(); N + 1];
        for i in 0..M {
            G[a[i]].insert(b[i]);
            G[b[i]].insert(a[i]);
        }
        G
    };
    fn f(x: usize, dist: usize, color: usize,
        G: &Vec<std::collections::HashSet<usize>>, res: &mut Vec<usize>, reacheable: &mut Vec<Vec<bool>>) {
        if reacheable[x][dist] {
            reacheable[x][dist] = false;
            if res[x] == 0 { res[x] = color; }
            if dist > 0 {
                for &y in &G[x] { f(y, dist - 1, color, &G, res, reacheable); }
            }
        }
    }
    let mut res = vec![0; N + 1];
    let mut reacheable = vec![vec![true; 11]; N + 1];
    for i in (0..Q).rev() { f(v[i], d[i], c[i], &G, &mut res, &mut reacheable); }
    let ans = res[1..].iter()
        .map(std::string::ToString::to_string)
        .collect::<Vec<_>>()
        .join("\n");

    println!("{}", ans);
}

Submission Info

Submission Time
Task B - Splatter Painting
User wotsushi
Language Rust (1.15.1)
Score 700
Code Size 2641 Byte
Status
Exec Time 339 ms
Memory 78460 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt
Subtask1 200 / 200 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt
All 500 / 500 00_example_01.txt, 00_example_02.txt, 10_01.txt, 10_02.txt, 10_03.txt, 10_04.txt, 10_05.txt, 10_06.txt, 10_07.txt, 10_08.txt, 10_09.txt, 10_10.txt, 10_11.txt, 10_12.txt, 10_13.txt, 10_14.txt, 10_15.txt, 10_16.txt, 10_17.txt, 20_01.txt, 20_02.txt, 20_03.txt, 20_04.txt, 20_05.txt, 20_06.txt, 20_07.txt, 20_08.txt, 20_09.txt, 20_10.txt, 20_11.txt, 20_12.txt, 20_13.txt, 20_14.txt, 20_15.txt, 20_16.txt
Case Name Status Exec Time Memory
00_example_01.txt 2 ms 4352 KB
00_example_02.txt 2 ms 4352 KB
10_01.txt 2 ms 4352 KB
10_02.txt 2 ms 4352 KB
10_03.txt 2 ms 4352 KB
10_04.txt 2 ms 4352 KB
10_05.txt 3 ms 4352 KB
10_06.txt 2 ms 4352 KB
10_07.txt 2 ms 4352 KB
10_08.txt 5 ms 4352 KB
10_09.txt 5 ms 4352 KB
10_10.txt 5 ms 4352 KB
10_11.txt 5 ms 4352 KB
10_12.txt 5 ms 4352 KB
10_13.txt 4 ms 4352 KB
10_14.txt 4 ms 4352 KB
10_15.txt 3 ms 4352 KB
10_16.txt 5 ms 4352 KB
10_17.txt 5 ms 4352 KB
20_01.txt 281 ms 70268 KB
20_02.txt 291 ms 70268 KB
20_03.txt 291 ms 70268 KB
20_04.txt 28 ms 8444 KB
20_05.txt 4 ms 4352 KB
20_06.txt 24 ms 20732 KB
20_07.txt 4 ms 4352 KB
20_08.txt 23 ms 10492 KB
20_09.txt 4 ms 4352 KB
20_10.txt 20 ms 8444 KB
20_11.txt 28 ms 10492 KB
20_12.txt 135 ms 68092 KB
20_13.txt 214 ms 72316 KB
20_14.txt 224 ms 72316 KB
20_15.txt 321 ms 78204 KB
20_16.txt 339 ms 78460 KB