Submission #5745122


Source Code Expand

Copy
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let v = read_vec::<usize>();
    let (n, m) = (v[0], v[1]);
    let mut graph = vec![vec![]; n];
    for i in 0..m {
        let v = read_vec::<usize>();
        let (a, b) = (v[0] - 1, v[1] - 1);
        graph[a].push(b);
        graph[b].push(a);
    }
    let q = read::<usize>();
    let mut queries = vec![];
    for i in 0..q {
        let v = read_vec::<usize>();
        queries.push((v[0] - 1, v[1], v[2] as i64));
    }
    let mut color = vec![0; n]; // -1 is uncolorerd
    let mut checked = vec![-1i64; n]; // 0 is unchecked;
    for &(v, d, c) in queries.iter().rev() {
        let mut que = VecDeque::new();
        que.push_back((v, 0));
        while let Some((cur_v, dist)) = que.pop_front() {
            checked[cur_v] = (d - dist) as i64;
            if color[cur_v] == 0 {
                color[cur_v] = c;
            }
            if dist + 1 <= d {
                for &next_v in graph[cur_v].iter() {
                    if checked[next_v] >= (d - (dist + 1)) as i64 {
                        continue;
                    }
                    que.push_back((next_v, dist + 1));
                }
            }
        }
    }
    for i in 0..n {
        println!("{:?}", color[i]);
    }
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

Submission Info

Submission Time
Task B - Splatter Painting
User ryoryoryo111
Language Rust (1.15.1)
Score 700
Code Size 1922 Byte
Status
Exec Time 278 ms
Memory 22612 KB

Compile Error

warning: unused variable: `i`, #[warn(unused_variables)] on by default
  --> ./Main.rs:22:9
   |
22 |     for i in 0..m {
   |         ^

warning: unused variable: `i`, #[warn(unused_variables)] on by default
  --> ./Main.rs:30:9
   |
30 |     for i in 0..q {
   |         ^

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 5 ms 4352 KB
10_08.txt 7 ms 4352 KB
10_09.txt 7 ms 4352 KB
10_10.txt 7 ms 4352 KB
10_11.txt 7 ms 4352 KB
10_12.txt 7 ms 4352 KB
10_13.txt 6 ms 4352 KB
10_14.txt 6 ms 4352 KB
10_15.txt 5 ms 4352 KB
10_16.txt 7 ms 4352 KB
10_17.txt 7 ms 4352 KB
20_01.txt 268 ms 16976 KB
20_02.txt 272 ms 16984 KB
20_03.txt 270 ms 16984 KB
20_04.txt 42 ms 9464 KB
20_05.txt 5 ms 4352 KB
20_06.txt 161 ms 10620 KB
20_07.txt 6 ms 4352 KB
20_08.txt 51 ms 8444 KB
20_09.txt 6 ms 4352 KB
20_10.txt 37 ms 8444 KB
20_11.txt 59 ms 9404 KB
20_12.txt 204 ms 12796 KB
20_13.txt 245 ms 16344 KB
20_14.txt 248 ms 16976 KB
20_15.txt 272 ms 22612 KB
20_16.txt 278 ms 22612 KB