#1194997 (Rust) No.5025 Forest Fire

• 問題: No.5025 Forest Fire
• ユーザー: shim0
• 提出日時: 2026-10-24 15:35:25
• 言語: Rust (1.99.0 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 6 ms / 2,000 ms
• コード長: 3,387 bytes
• コンパイル時間: 4,389 ms
• コンパイル使用メモリ: 190,372 KB
• 実行使用メモリ: 9,928 KB
• スコア: 158,364,384
• 最終ジャッジ日時: 2026-10-24 15:36:28
• 合計ジャッジ時間: 59,942 ms
• ジャッジサーバーID （参考情報）: judge5_0 / <nil>

ファイルパターン	結果
other	AC * 50

ソースコード

use ac_library::Dsu;
use proconio::{input, marker::Bytes};

const DRY_THRESHOLD: u8 = 5;

fn neighbors(v: usize, n: usize) -> impl Iterator<Item = usize> {
    let (r, c) = (v / n, v % n);
    [
        (r > 0).then(|| v - n),
        (r + 1 < n).then(|| v + n),
        (c > 0).then(|| v - 1),
        (c + 1 < n).then(|| v + 1),
    ]
    .into_iter()
    .flatten()
}

fn largest_group(active: &[bool], n: usize) -> Vec<usize> {
    let mut dsu = Dsu::new(n * n);
    for v in 0..n * n {
        if active[v] {
            for u in neighbors(v, n) {
                if active[u] {
                    dsu.merge(v, u);
                }
            }
        }
    }
    let mut best = Vec::new();
    for group in dsu.groups() {
        if active[group[0]] && group.len() > best.len() {
            best = group;
        }
    }
    best
}

// Test actual connected components after removing this row or column.
fn is_balanced(group: &[usize], n: usize, axis: usize, line: usize) -> bool {
    let coordinate = |v: usize| if axis == 0 { v / n } else { v % n };
    let mut unseen = vec![false; n * n];
    for &v in group {
        unseen[v] = coordinate(v) != line;
    }
    let mut stack = Vec::with_capacity(group.len());
    for &start in group {
        if !unseen[start] {
            continue;
        }
        unseen[start] = false;
        stack.push(start);
        let mut size = 0;
        while let Some(v) = stack.pop() {
            size += 1;
            if size * 2 > group.len() {
                return false;
            }
            for u in neighbors(v, n) {
                if unseen[u] {
                    unseen[u] = false;
                    stack.push(u);
                }
            }
        }
    }
    true
}

fn choose_cut(group: &[usize], n: usize) -> Option<Vec<usize>> {
    let mut best: Option<Vec<usize>> = None;
    // First encountered wins ties: rows, then columns, in ascending order.
    for axis in 0..2 {
        for line in 0..n {
            let cut: Vec<_> = group
                .iter()
                .copied()
                .filter(|&v| (if axis == 0 { v / n } else { v % n }) == line)
                .collect();
            if cut.is_empty() || best.as_ref().is_some_and(|b| cut.len() >= b.len()) {
                continue;
            }
            if is_balanced(group, n, axis, line) {
                best = Some(cut);
            }
        }
    }
    best
}

fn main() {
    input! { n: usize, k: usize, rows: [Bytes; n] }
    let mut active = Vec::with_capacity(n * n);
    for row in rows {
        assert_eq!(row.len(), n);
        active.extend(row.into_iter().map(|d| d - b'0' >= DRY_THRESHOLD));
    }
    let mut answer = Vec::new();
    while answer.len() < k {
        let group = largest_group(&active, n);
        if group.is_empty() {
            break;
        }
        // No alternative cutting rule has been specified if no line qualifies.
        let mut cut = choose_cut(&group, n)
            .expect("No straight cut satisfies the specified half-size condition");
        cut.sort_unstable();
        for v in cut.into_iter().take(k - answer.len()) {
            active[v] = false;
            answer.push(v);
        }
    }
    eprintln!("remaining_cut_budget: {}", k - answer.len());
    println!("{}", answer.len());
    for v in answer {
        println!("{} {}", v / n, v % n);
    }
}