Submission #1301935
Source Code Expand
use std::fmt::Debug; use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use std::usize; use std::cmp; use std::collections::vec_deque::VecDeque; use std::i64::MAX; pub struct Edge { pub to: usize, pub rev: usize, pub cap: i64, } struct Dinitz { g: Vec<Vec<Edge>>, level: Vec<i32>, iter: Vec<usize>, } impl Dinitz { fn new(v: usize) -> Dinitz { let mut g: Vec<Vec<Edge>> = Vec::new(); for _ in 0..v { g.push(Vec::new()); } Dinitz { g: g, level: vec![0;v], iter: vec![0;v], } } fn add_edge(&mut self, from: usize, to: usize, cap: i64) { let to_len = self.g[to].len(); let from_len = self.g[from].len(); self.g[from].push(Edge { to: to, rev: to_len, cap: cap, }); self.g[to].push(Edge { to: from, rev: from_len, cap: 0, }); } fn dfs(&mut self, v: usize, t: usize, f: i64) -> i64 { if v == t { return f; } while self.iter[v] < self.g[v].len() { let (e_cap, e_to, e_rev); { let ref e = self.g[v][self.iter[v]]; e_cap = e.cap; e_to = e.to; e_rev = e.rev; } if e_cap > 0 && self.level[v] < self.level[e_to] { let d = self.dfs(e_to, t, cmp::min(f, e_cap)); if d > 0 { { let ref mut e = self.g[v][self.iter[v]]; e.cap -= d; } { let ref mut rev_edge = self.g[e_to][e_rev]; rev_edge.cap += d; } return d; } } self.iter[v] += 1; } return 0; } fn bfs(&mut self, s: usize) { let v = self.level.len(); self.level = vec![-1;v]; self.level[s] = 0; let mut deque = VecDeque::new(); deque.push_back(s); while !deque.is_empty() { let v = deque.pop_front().unwrap(); for e in &self.g[v] { if e.cap > 0 && self.level[e.to] < 0 { self.level[e.to] = self.level[v] + 1; deque.push_back(e.to); } } } } fn max_flow(&mut self, s: usize, t: usize) -> i64 { let v = self.level.len(); let mut flow: i64 = 0; loop { self.bfs(s); if self.level[t] < 0 { return flow; } self.iter = vec![0;v]; loop { let f = self.dfs(s, t, MAX); if f == 0 { break; } flow += f; } } } } fn main() { let mut sc = Scanner::new(); let n = sc.parse::<usize>(); let g = sc.parse::<usize>(); let e = sc.parse::<usize>(); let v = n + 1; let mut dinitz = Dinitz::new(v); for _ in 0..g { let p = sc.parse::<usize>(); dinitz.add_edge(p, n, 1); } for _ in 0..e { let a = sc.parse::<usize>(); let b = sc.parse::<usize>(); dinitz.add_edge(a, b, 1); dinitz.add_edge(b, a, 1); } let ans = dinitz.max_flow(0, n); println!("{}", ans); } struct Scanner { stdin: Stdin, buf: Vec<u8>, } impl Scanner { fn new() -> Scanner { Scanner { stdin: io::stdin(), buf: Vec::with_capacity(256), } } fn parse<T: FromStr>(&mut self) -> T where <T as FromStr>::Err: Debug { self.buf.clear(); let mut it = self.stdin.lock().bytes(); let mut c = it.next().unwrap().unwrap(); while c == ' ' as u8 || c == '\n' as u8 { c = it.next().unwrap().unwrap(); } while !(c == ' ' as u8 || c == '\n' as u8) { self.buf.push(c); c = it.next().unwrap().unwrap(); } str::from_utf8(&self.buf).unwrap().parse::<T>().unwrap() } }
Submission Info
Submission Time | |
---|---|
Task | D - 浮気予防 |
User | kenkoooo |
Language | Rust (1.15.1) |
Score | 100 |
Code Size | 4514 Byte |
Status | AC |
Exec Time | 3 ms |
Memory | 4352 KB |
Judge Result
Set Name | part | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 99 / 99 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
part | test_01_AB.txt, test_02_AB.txt, test_03_AB.txt, test_04_AB.txt, test_05_AB.txt, test_06_AB.txt, test_07_AB.txt, test_08_AB.txt, test_09_AB.txt, test_10_AB.txt, test_11_AB.txt, test_12_AB.txt, test_13_AB.txt, test_14_AB.txt, test_15_AB.txt, test_16_AB.txt, test_17_AB.txt, test_18_AB.txt, test_19_AB.txt, test_20_AB.txt, test_21_AB.txt, test_22_AB.txt, test_23_AB.txt, test_24_AB.txt, test_25_AB.txt, test_41_AB.txt, test_47_AB.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, test_01_AB.txt, test_02_AB.txt, test_03_AB.txt, test_04_AB.txt, test_05_AB.txt, test_06_AB.txt, test_07_AB.txt, test_08_AB.txt, test_09_AB.txt, test_10_AB.txt, test_11_AB.txt, test_12_AB.txt, test_13_AB.txt, test_14_AB.txt, test_15_AB.txt, test_16_AB.txt, test_17_AB.txt, test_18_AB.txt, test_19_AB.txt, test_20_AB.txt, test_21_AB.txt, test_22_AB.txt, test_23_AB.txt, test_24_AB.txt, test_25_AB.txt, test_26_A.txt, test_27_A.txt, test_28_A.txt, test_29_A.txt, test_30_A.txt, test_31_A.txt, test_32_A.txt, test_33_A.txt, test_34_A.txt, test_35_A.txt, test_36_A.txt, test_37_A.txt, test_38_A.txt, test_39_A.txt, test_40_A.txt, test_41_AB.txt, test_42_A.txt, test_43_A.txt, test_44_A.txt, test_45_A.txt, test_46_A.txt, test_47_AB.txt, test_48_A.txt, test_49_A.txt, test_50_A.txt, test_51_A.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 2 ms | 4352 KB |
sample_02.txt | AC | 2 ms | 4352 KB |
sample_03.txt | AC | 2 ms | 4352 KB |
sample_04.txt | AC | 2 ms | 4352 KB |
sample_05.txt | AC | 2 ms | 4352 KB |
test_01_AB.txt | AC | 2 ms | 4352 KB |
test_02_AB.txt | AC | 2 ms | 4352 KB |
test_03_AB.txt | AC | 2 ms | 4352 KB |
test_04_AB.txt | AC | 2 ms | 4352 KB |
test_05_AB.txt | AC | 2 ms | 4352 KB |
test_06_AB.txt | AC | 2 ms | 4352 KB |
test_07_AB.txt | AC | 2 ms | 4352 KB |
test_08_AB.txt | AC | 2 ms | 4352 KB |
test_09_AB.txt | AC | 2 ms | 4352 KB |
test_10_AB.txt | AC | 2 ms | 4352 KB |
test_11_AB.txt | AC | 2 ms | 4352 KB |
test_12_AB.txt | AC | 2 ms | 4352 KB |
test_13_AB.txt | AC | 2 ms | 4352 KB |
test_14_AB.txt | AC | 2 ms | 4352 KB |
test_15_AB.txt | AC | 2 ms | 4352 KB |
test_16_AB.txt | AC | 2 ms | 4352 KB |
test_17_AB.txt | AC | 2 ms | 4352 KB |
test_18_AB.txt | AC | 2 ms | 4352 KB |
test_19_AB.txt | AC | 2 ms | 4352 KB |
test_20_AB.txt | AC | 2 ms | 4352 KB |
test_21_AB.txt | AC | 2 ms | 4352 KB |
test_22_AB.txt | AC | 2 ms | 4352 KB |
test_23_AB.txt | AC | 2 ms | 4352 KB |
test_24_AB.txt | AC | 2 ms | 4352 KB |
test_25_AB.txt | AC | 2 ms | 4352 KB |
test_26_A.txt | AC | 3 ms | 4352 KB |
test_27_A.txt | AC | 3 ms | 4352 KB |
test_28_A.txt | AC | 3 ms | 4352 KB |
test_29_A.txt | AC | 3 ms | 4352 KB |
test_30_A.txt | AC | 3 ms | 4352 KB |
test_31_A.txt | AC | 3 ms | 4352 KB |
test_32_A.txt | AC | 2 ms | 4352 KB |
test_33_A.txt | AC | 3 ms | 4352 KB |
test_34_A.txt | AC | 2 ms | 4352 KB |
test_35_A.txt | AC | 2 ms | 4352 KB |
test_36_A.txt | AC | 2 ms | 4352 KB |
test_37_A.txt | AC | 2 ms | 4352 KB |
test_38_A.txt | AC | 2 ms | 4352 KB |
test_39_A.txt | AC | 2 ms | 4352 KB |
test_40_A.txt | AC | 2 ms | 4352 KB |
test_41_AB.txt | AC | 2 ms | 4352 KB |
test_42_A.txt | AC | 2 ms | 4352 KB |
test_43_A.txt | AC | 2 ms | 4352 KB |
test_44_A.txt | AC | 2 ms | 4352 KB |
test_45_A.txt | AC | 2 ms | 4352 KB |
test_46_A.txt | AC | 2 ms | 4352 KB |
test_47_AB.txt | AC | 2 ms | 4352 KB |
test_48_A.txt | AC | 2 ms | 4352 KB |
test_49_A.txt | AC | 2 ms | 4352 KB |
test_50_A.txt | AC | 2 ms | 4352 KB |
test_51_A.txt | AC | 2 ms | 4352 KB |