AtCoder Beginner Contest 299 E

https://atcoder.jp/contests/abc299/tasks/abc299_e

最初に全部黒にして、dより内側は全て白くします。そこで、dのところが全て白でないかを調べます。簡単そうですが、トラップがあります。

// Nearest Black Vertex
#![allow(non_snake_case)]

use std::collections::{VecDeque, HashSet, HashMap};


//////////////////// library ////////////////////

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

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


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);

struct Graph {
    g: Vec<Vec<usize>>
}

impl Graph {
    fn create_from_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<usize>> = (0..N).map(|_| vec![]).collect();
        for (v, w) in edges.into_iter() {
            g[v].push(w);
            g[w].push(v)
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>, Vec<(usize, usize)>) {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let edges: Vec<Edge> = (0..M).map(|_| read_vec::<Node>()).
                                    map(|v| (v[0]-1, v[1]-1)).collect();
    let K: usize = read();
    let mins: Vec<(usize, usize)> = (0..K).map(|_| read_vec::<usize>()).
                                            map(|v| (v[0]-1, v[1])).collect();
    (N, edges, mins)
}

fn is_duplicated(mins: &Vec<(usize, usize)>) -> bool {
    let mut m: HashMap<usize, usize> = HashMap::new();
    for &(v, d) in mins.iter() {
        if let Some(value) = m.get_mut(&v) {
            if *value != v {
                return true
            }
        }
        else {
            m.insert(v, d);
        }
    }
    false
}

fn create_distances(v0: Node, d: usize, graph: &Graph) -> Vec<(Node, usize)> {
    let mut dists: Vec<(Node, usize)> = Vec::new();
    let mut queue = VecDeque::new();
    let mut visited: HashSet<Node> = HashSet::new();
    dists.push((v0, 0));
    queue.push_back((v0, 0usize));
    visited.insert(v0);
    while !queue.is_empty() {
        let (v1, d1) = queue.pop_front().unwrap();
        if d1 == d {
            continue
        }
        
        for v2 in graph.g[v1].iter() {
            if !visited.contains(v2) {
                dists.push((*v2, d1 + 1));
                queue.push_back((*v2, d1 + 1));
                visited.insert(*v2);
            }
        }
    }
    dists
}

fn create_equations_and_inequations(
                table: Vec<(usize, Vec<(Node, usize)>)>, N: usize
                                    ) -> (Vec<i32>, Vec<Vec<Node>>) {
    let mut equations: Vec<i32> = (0..N).map(|_| 1).collect();
    let mut inequations: Vec<Vec<Node>> = Vec::new();
    for (max_d, dists) in table.into_iter() {
        let mut inequation: Vec<Node> = Vec::new();
        for (v1, d) in dists.into_iter() {
            if d < max_d {
                equations[v1] = 0
            }
            else {
                inequation.push(v1)
            }
        }
        inequations.push(inequation)
    }
    (equations, inequations)
}

fn conflicts(inequations: Vec<Vec<Node>>, equations: &Vec<i32>) -> bool {
    for v in inequations.into_iter() {
        if v.into_iter().all(|i| equations[i] == 0) {
            return true
        }
    }
    false
}

fn f(N: usize, edges: Vec<Edge>, mins: Vec<(usize, usize)>) {
    if is_duplicated(&mins) {
        println!("No");
        return
    }
    
    let graph = Graph::create_from_edges(N, edges);
    let table: Vec<(usize, Vec<(Node, usize)>)> =
                    mins.into_iter().
                    map(|(v0, d)| (d, create_distances(v0, d, &graph))).
                    collect();
    let (equations, inequations) = create_equations_and_inequations(table, N);
    if conflicts(inequations, &equations) {
        println!("No")
    }
    else {
        let s = equations.iter().map(|n| n.to_string()).
                                collect::<Vec<String>>().join("");
        println!("Yes");
        println!("{}", s)
    }
}

fn main() {
    let (N, edges, mins) = read_input();
    f(N, edges, mins)
}