結果

問題 No.241 出席番号(1)
ユーザー hatoohatoo
提出日時 2017-11-12 20:44:41
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,280 bytes
コンパイル時間 11,974 ms
コンパイル使用メモリ 405,408 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-08 00:25:18
合計ジャッジ時間 13,512 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 1 ms
5,376 KB
testcase_16 AC 1 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 1 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 1 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 1 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 1 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet, BinaryHeap};
#[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] }
    }

    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(&mut self, s: usize, t: usize) -> usize {
        let mut flow = 0;
        let l = self.edges.len();
        loop {
            let f = self.dfs(s, t, usize::max_value(), &mut vec![false; l]);
            if f == 0 {
                break;
            }
            flow += f;
        }
        flow
    }

    fn dfs(&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(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(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");
    }
}
0