結果

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

ソースコード

diff #
raw source code 

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();
    while let Some(v) = stack.pop() {
        deg[v] = 0;
        c[v] = (0..4)
            .find(|&i| graph[v].iter().all(|&u| c[u] != i))
            .unwrap();
        for &u in &graph[v] {
            deg[u] = deg[u].saturating_sub(1);
            if deg[u] == 3 {
                stack.push(u);
            }
        }
    }

    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().map(|i| i + 1).join(" "));
}
0