結果

問題 No.3552 Triangular Coloring
コンテスト
ユーザー urectanc
提出日時 2026-05-23 00:11:50
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
WA  
実行時間 -
コード長 1,200 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,607 ms
コンパイル使用メモリ 205,356 KB
実行使用メモリ 35,696 KB
最終ジャッジ日時 2026-05-23 00:12:04
合計ジャッジ時間 4,447 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 6 RE * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::collections::HashSet;

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize, m: usize,
        edges: [(Usize1, Usize1); m],
    }

    let mut graph = vec![vec![]; n];
    let mut deg = vec![0usize; n];
    for &(u, v) in &edges {
        graph[u].push(v);
        graph[v].push(u);
        deg[u] += 1;
        deg[v] += 1;
    }

    let mut c = vec![!0; n];
    let mut stack = (0..n).filter(|&i| deg[i] == 3).collect_vec();
    for i in 0.. {
        let mut update = HashSet::new();
        for v in stack.drain(..) {
            deg[v] = 0;
            c[v] = i % 4;
            for &u in &graph[v] {
                deg[u] = deg[u].saturating_sub(1);
                update.insert(u);
            }
        }

        for v in update {
            if deg[v] == 3 {
                stack.push(v);
            }
        }

        if stack.is_empty() {
            break;
        }
    }

    for v in 0..n {
        if c[v] == !0 {
            c[v] = (0..4)
                .find(|&i| graph[v].iter().all(|&u| c[u] != i))
                .unwrap();
        }
    }

    println!("Yes");
    println!("{}", c.iter().join(" "));
}
0