#1128490 (Rust) No.1123 Afforestation

• 問題: No.1123 Afforestation
• ユーザー: koba-e964
• 提出日時: 2025-10-22 22:47:26
• 言語: Rust (1.83.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 10,273 bytes
• コンパイル時間: 13,792 ms
• コンパイル使用メモリ: 398,832 KB
• 実行使用メモリ: 21,028 KB
• 最終ジャッジ日時: 2025-10-22 22:47:47
• 合計ジャッジ時間: 19,450 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	-- * 3
other	AC * 4 TLE * 1 -- * 85

コンパイルメッセージ

warning: unused variable: `cost`
   --> src/main.rs:323:17
    |
323 |     if let Some(cost) = mcc.min_cost() {
    |                 ^^^^ help: if this is intentional, prefix it with an underscore: `_cost`
    |
    = note: `#[warn(unused_variables)]` on by default

ソースコード

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes.by_ref().map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr,) => {};
    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };
    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };
    ($next:expr, usize1) => (read_value!($next, usize) - 1);
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

// Minimum cost flow.
// Verified by: yukicoder No.1301 Strange Graph Shortest Path
//              (https://yukicoder.me/submissions/590401)
//              AtCoder Library Practice Contest - E
//              (https://atcoder.jp/contests/practice2/submissions/22478556)
//              ACL Contest 1 - C
//              (https://atcoder.jp/contests/acl1/submissions/23898415)
type Cap = isize;
type Cost = i64;
#[derive(Debug, Clone, Copy)]
struct Edge {
    to: usize,
    cap: Cap,
    cost: Cost,
    rev: usize, // rev is the position of reverse edge in graph[to]
}

#[derive(Debug, Clone)]
struct MinCostFlow {
    n: usize,
    graph: Vec<Vec<Edge>>,
    h: Vec<Cost>, // potential,
    dist: Vec<Cost>, // minimum distance
    prev: Vec<(usize, usize)>, // previous vertex and edge
}

impl MinCostFlow {
    // Initializes this solver. n is the number of vertices.
    fn new(n: usize) -> Self {
        MinCostFlow {
            n: n,
            graph: vec![vec![]; n],
            h: vec![0; n],
            dist: vec![0; n],
            prev: vec![(0, 0); n],
        }
    }
    fn add_edge(&mut self, from: usize, to: usize, cap: Cap, cost: Cost) {
        let fst = Edge {
            to: to,
            cap: cap,
            cost: cost,
            rev: self.graph[to].len(),
        };
        self.graph[from].push(fst);
        let snd = Edge {
            to: from,
            cap: 0,
            cost: -cost,
            rev: self.graph[from].len() - 1,
        };
        self.graph[to].push(snd);
    }
    // Calcucates the minimum cost flow
    // whose source is s, sink is t, and flow is f.
    fn min_cost_flow(&mut self, s: usize, t: usize, mut f: Cap) -> Cost {
        let n = self.n;
        let inf: Cost = std::i64::MAX / 10; // ?????
        let mut res = 0;
        let h = &mut self.h;
        let dist = &mut self.dist;
        while f > 0 {
            let mut que = std::collections::BinaryHeap::<(Cost, usize)>::new();
            for i in 0..n {
                dist[i] = inf;
            }
            dist[s] = 0;
            que.push((0, s));
            while let Some((d, v)) = que.pop() {
                let d = -d;
                if dist[v] < d {
                    continue;
                }
                for (i, &e) in self.graph[v].iter().enumerate() {
                    if e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to] {
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        self.prev[e.to] = (v, i);
                        que.push((-dist[e.to], e.to));
                    }
                }
            }
            if dist[t] == inf {
            return -1; // Cannot add flow anymore
            }
            for i in 0..n {
                h[i] += dist[i];
            }
            // Add flow fully
            let mut d = f;
            let mut i = t;
            while i != s {
                let (pv, pe) = self.prev[i];
            d = std::cmp::min(d, self.graph[pv][pe].cap);
                i = pv;
            }
            f -= d;
            res += d as Cost * h[t];
            i = t;
            while i != s {
                let (pv, pe) = self.prev[i];
                self.graph[pv][pe].cap -= d;
                let erev = self.graph[pv][pe].rev;
            self.graph[i][erev].cap += d;
                i = pv;
            }
        }
        return res;
    }
}

// Handles minimum cost circulation problems.
// ref: https://atcoder.jp/contests/abc231/submissions/27857324
// ref: https://gist.github.com/brunodccarvalho/fb9f2b47d7f8469d209506b336013473
// ref: https://people.orie.cornell.edu/dpw/orie633/LectureNotes/lecture11.pdf
// Depends on: graph/MinCostFlow.rs
// Verified by:
// - https://atcoder.jp/contests/practice2/submissions/70013984
// - https://atcoder.jp/contests/practice2/submissions/70014032
pub struct MinCostCirc {
    mcf: MinCostFlow,
    sup: Vec<Cap>,
    cost: Cost,
    edges: Vec<(usize, usize, Cap)>, // (u, index in graph[u], cap)
}

impl MinCostCirc {
    pub fn new(n: usize) -> Self {
        let mcf = MinCostFlow::new(2 + n);
        MinCostCirc {
            mcf: mcf,
            sup: vec![0; n],
            cost: 0,
            edges: vec![],
        }
    }
    pub fn add_edge(&mut self, a: usize, b: usize, (dem, cap): (Cap, Cap), cost: Cost) {
        assert!(dem <= cap);
        if cost >= 0 {
            self.add_edge_inner(a, b, (dem, cap), cost, false);
        } else {
            self.add_edge_inner(b, a, (-cap, -dem), -cost, true);
        }
    }
    fn add_edge_inner(
        &mut self, a: usize, b: usize,
        (dem, cap): (Cap, Cap), cost: Cost, flipped: bool,
    ) {
        assert!(dem <= cap);
        assert!(cost >= 0);
        self.cost += dem as Cost * cost;
        let index = self.mcf.graph[2 + if flipped { b } else { a }].len();
        self.mcf.add_edge(2 + a, 2 + b, cap - dem, cost);
        self.sup[b] += dem;
        self.sup[a] -= dem;
        if flipped {
            // Let e' = (a -> b) and e = (b -> a). (Note that the original edge was b -> a.)
            // If after min_cost() e.cap = x holds,
            // the actual flow on the edge e is cap - x = cap - e.cap
            self.edges.push((b, index, -dem));
        } else {
            // If after min_cost() e.cap = cap - dem - x holds,
            // the actual flow is dem + x = cap - e.cap
            self.edges.push((a, index, cap));
        }
    }
    pub fn min_cost(&mut self) -> Option<Cost> {
        let s: Cap = self.sup.iter().sum();
        if s != 0 {
            return None;
        }
        let n = self.sup.len();
        let sup = &self.sup;
        let mut f = 0;
        for i in 0..n {
            if sup[i] > 0 {
                self.mcf.add_edge(0, 2 + i, sup[i], 0);
                f += sup[i];
            }
            if sup[i] < 0 {
                self.mcf.add_edge(2 + i, 1, -sup[i], 0);
            }
        }
        let cost = self.mcf.min_cost_flow(0, 1, f);
        if cost < 0 {
            None
        } else {
            Some(cost + self.cost)
        }
    }
    // Call it only after calling min_cost.
    #[allow(unused)]
    pub fn sol(&self) -> Vec<(usize, usize, Cap)> {
        let mut ans = vec![];
        for &(i, j, cap) in &self.edges {
            let e = &self.mcf.graph[2 + i][j];
            let amount = cap - e.cap;
            if amount != 0 && e.to >= 2 {
                ans.push((i, e.to - 2, amount));
            }
        }
        ans
    }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

fn solve() {
    #[allow(unused)]
    let out = std::io::stdout();
    #[allow(unused)]
    let mut out = BufWriter::new(out.lock());
    #[allow(unused)]
    macro_rules! puts {($($format:tt)*) => (let _ = write!(out,$($format)*););}
    #[allow(unused)]
    macro_rules! putvec {
        ($v:expr) => {
            for i in 0..$v.len() {
                puts!("{}{}", $v[i], if i + 1 == $v.len() {"\n"} else {" "});
            }
        }
    }
    macro_rules! fail {
        () => {
            println!(":(");
            return;
        }
    }
    input! {
        h: usize, w: usize,
        a: [usize; h],
        b: [usize; w],
        k: usize,
        xy: [(usize1, usize1); k],
    }
    if a.iter().sum::<usize>() != b.iter().sum::<usize>() {
        fail!();
    }
    let mut ai = vec![];
    for i in 0..h {
        ai.push((a[i], i));
    }
    ai.sort(); ai.reverse();
    let mut bi = vec![];
    for i in 0..w {
        bi.push((b[i], i));
    }
    bi.sort(); bi.reverse();
    let mut ans = vec![vec!['.'; w]; h];
    for (a, i) in ai {
        if a == 0 { continue; }
        if bi[a - 1].0 == 0 {
            fail!();
        }
        for j in 0..a {
            bi[j].0 -= 1;
            ans[i][bi[j].1] = 'o';
        }
        bi.sort(); bi.reverse();
    }
    let mut mcc = MinCostCirc::new(h + w);
    for i in 0..k {
        let (x, y) = xy[i];
        if ans[x][y] == 'o' {
            mcc.add_edge(x, h + y, (-1, -1), 0);
        }
        ans[x][y] = 'x';
    }
    for i in 0..h {
        for j in 0..w {
            if ans[i][j] == 'x' {
                continue;
            }
            mcc.add_edge(i, h + j, if ans[i][j] == 'o' {
                (-1, 0)
            } else {
                (0, 1)
            }, 0);
        }
    }
    if let Some(cost) = mcc.min_cost() {
        let sol = mcc.sol();
        for (from, to, flow) in sol {
            if ans[from][to - h] == 'x' {
                continue;
            }
            if flow == -1 {
                ans[from][to - h] = '.';
            }
            if flow == 1 {
                ans[from][to - h] = 'o';
            }
        }
        puts!("Yay!\n");
        for i in 0..h {
            puts!("{}\n", ans[i].iter().cloned().collect::<String>());
        }
    } else {
        fail!();
    }
}