#216548 (Rust) No.241 出席番号(1)

• 問題: No.241 出席番号(1)
• ユーザー: hatoo
• 提出日時: 2017-11-12 23:14:34
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 6,103 bytes
• コンパイル時間: 11,510 ms
• コンパイル使用メモリ: 378,748 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-30 21:43:01
• 合計ジャッジ時間: 12,892 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	0 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	0 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	1 ms; 5,248 KB
testcase_21	AC	1 ms; 5,248 KB
testcase_22	AC	1 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	1 ms; 5,248 KB
testcase_25	AC	1 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	1 ms; 5,248 KB
testcase_28	AC	1 ms; 5,248 KB
testcase_29	AC	2 ms; 5,248 KB
testcase_30	AC	1 ms; 5,248 KB
testcase_31	AC	1 ms; 5,248 KB

コンパイルメッセージ

warning: methods `max_flow_ff` and `dfs_ff` are never used
   --> src/main.rs:169:8
    |
88  | impl Flow {
    | --------- methods in this implementation
...
169 |     fn max_flow_ff(&mut self, s: usize, t: usize) -> usize {
    |        ^^^^^^^^^^^
...
182 |     fn dfs_ff(&mut self, v: usize, t: usize, f: usize, used: &mut [bool]) -> usize {
    |        ^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

ソースコード

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}


struct Flow {
    // to, capacity, rev
    edges: Vec<Vec<(usize, usize, usize)>>,
}

impl Flow {
    fn new(max_size: usize) -> Flow {
        Flow { edges: vec![Vec::new(); max_size + 1] }
    }

    fn add_edge(&mut self, from: usize, to: usize, cap: usize) {
        let from_rev = self.edges[to].len();
        let to_rev = self.edges[from].len();

        self.edges[from].push((to, cap, from_rev));
        self.edges[to].push((from, 0, to_rev));
    }

    fn max_flow_dinic(&mut self, s: usize, t: usize) -> usize {
        let mut flow = 0;
        loop {
            let level = self.bfs_dinic(s);
            let mut iter = vec![0; self.edges.len()];
            if level[t].is_none() {
                return flow;
            }

            loop {
                let f = self.dfs_dinic(s, t, usize::max_value(), &level, &mut iter);
                if f == 0 {
                    break;
                }
                flow += f;
            }
        }
    }

    fn bfs_dinic(&self, s: usize) -> Vec<Option<usize>> {
        let mut level = vec![None; self.edges.len()];
        let mut que = VecDeque::new();

        level[s] = Some(0);
        que.push_back(s);

        while !que.is_empty() {
            let v = que.pop_front().unwrap();
            let l = Some(level[v].unwrap() + 1);

            for &(to, cap, _) in &self.edges[v] {
                if cap > 0 && level[to].is_none() {
                    level[to] = l;
                    que.push_back(to);
                }
            }
        }
        level
    }

    fn dfs_dinic(
        &mut self,
        v: usize,
        t: usize,
        f: usize,
        level: &[Option<usize>],
        iter: &mut [usize],
    ) -> usize {
        if v == t {
            return f;
        }

        for i in iter[v]..self.edges[v].len() {
            iter[v] = i;

            let (to, cap, rev) = self.edges[v][i];
            if cap > 0 && level[v].unwrap() < level[to].unwrap_or(0) {
                let d = self.dfs_dinic(to, t, min(f, cap), level, iter);
                if d > 0 {
                    self.edges[v][i].1 -= d;
                    self.edges[to][rev].1 += d;
                    return d;
                }
            }
        }
        0
    }

    fn max_flow_ff(&mut self, s: usize, t: usize) -> usize {
        let mut flow = 0;
        let l = self.edges.len();
        loop {
            let f = self.dfs_ff(s, t, usize::max_value(), &mut vec![false; l]);
            if f == 0 {
                break;
            }
            flow += f;
        }
        flow
    }

    fn dfs_ff(&mut self, v: usize, t: usize, f: usize, used: &mut [bool]) -> usize {
        if v == t {
            return f;
        }
        used[v] = true;

        for i in 0..self.edges[v].len() {
            let (to, cap, rev) = self.edges[v][i];
            if !used[to] && cap > 0 {
                let d = self.dfs_ff(to, t, min(f, cap), used);
                if d > 0 {
                    self.edges[v][i].1 -= d;
                    self.edges[to][rev].1 += d;
                    return d;
                }
            }
        }
        0
    }
}

fn main() {
    let n = get!(usize);
    let a = get!(usize; n);

    let mut flow = Flow::new(4 * n + 1);

    let s = 0;
    let t = 3 * n + 1;
    for i in 0..n {
        flow.add_edge(0, i + 1, 1);
        flow.add_edge(n + 1 + 2 * i, n + 1 + 2 * i + 1, 1);
        flow.add_edge(n + 1 + 2 * i + 1, t, 1);
        for k in 0..n {
            if k == a[i] {
                continue;
            }
            flow.add_edge(i + 1, n + 1 + 2 * k, 1);
        }
    }

    if flow.max_flow_dinic(s, t) == n {
        for i in 0..n {
            for k in 0..flow.edges[i + 1].len() {
                let to = flow.edges[i + 1][k].0;
                let rev = flow.edges[i + 1][k].2;
                if flow.edges[to][rev].1 > 0 {
                    println!("{}", (to - 1 - n) / 2);
                    break;
                }
            }
        }
    } else {
        println!("-1");
    }
}