結果
問題 | No.583 鉄道同好会 |
ユーザー | aimy |
提出日時 | 2017-10-27 23:58:29 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 6,317 bytes |
コンパイル時間 | 12,902 ms |
コンパイル使用メモリ | 378,956 KB |
実行使用メモリ | 13,312 KB |
最終ジャッジ日時 | 2024-11-21 23:44:11 |
合計ジャッジ時間 | 13,639 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 1 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 7 ms
5,248 KB |
testcase_12 | AC | 10 ms
6,528 KB |
testcase_13 | AC | 10 ms
6,528 KB |
testcase_14 | AC | 10 ms
6,528 KB |
testcase_15 | AC | 11 ms
7,168 KB |
testcase_16 | AC | 23 ms
12,032 KB |
testcase_17 | AC | 27 ms
13,312 KB |
testcase_18 | AC | 27 ms
13,312 KB |
ソースコード
fn main() { let (n, m): (usize, usize) = get::tuple(); let edges: Vec<(usize, usize)> = get::tuples(m); let mut freq = vec![false; n]; for &(a, b) in &edges { freq[a] = true; freq[b] = true; } let map = freq.iter().scan(0,|a,&x| {if x {*a+=1; Some(*a)} else {Some(0)}}).collect::<Vec<_>>(); let edges = edges.iter().map(|&(a,b)| (map[a]-1,map[b]-1)).collect::<Vec<_>>(); let n = freq.iter().filter(|&&p|p).count(); let g = Graph::new_nonlabeled(n, &edges); if Graph::is_hitofude(&g) && Graph::is_connected(&g) { println!("YES"); } else { println!("NO"); } } struct Graph { size: usize, adj: Vec<Vec<(usize, isize)>> } impl Clone for Graph { fn clone(&self) -> Graph { Graph { size: self.size, adj: self.adj.clone() } } } #[allow(dead_code)] impl Graph { fn new_nonlabeled(n: usize, edges: &[(usize, usize)]) -> Graph { let edges = edges.iter().map(|&(a,b)|(a,b,0isize)).collect::<Vec<_>>(); Graph::new_labeled(n, &edges) } fn new_labeled(n: usize, edges: &[(usize, usize, isize)]) -> Graph { let mut g: Vec<Vec<(usize, isize)>> = vec![vec![]; n]; for &(a, b, c) in edges { g[a].push((b,c)); g[b].push((a,c)); // delete for digraph } Graph {size: n, adj: g} } fn is_connected(&self) -> bool { self.dfs(0).len() == self.size } fn size(&self) -> usize { self.size } fn edges(&self) -> Vec<(usize, usize, isize)> { let mut buf = vec![]; for (i, next) in self.adj.iter().enumerate() { for &(j, x) in next { buf.push((i, j, x)) } } buf } fn is_hitofude(&self) -> bool { let ploop = self.adj.iter().all(|vs|vs.len()%2==0); let pnloop = self.adj.iter().filter(|vs|vs.len()%2==1).count() == 2; ploop || pnloop } fn bellman_ford(&self, s: usize) -> Vec<isize> { const INF: isize = std::isize::MAX >> 1; let edges = self.edges(); let mut bf: Vec<isize> = vec![INF; self.size]; bf[s] = 0; for _ in 1 .. self.size { for &(v, w, c) in &edges { bf[w] = std::cmp::min(bf[w], bf[v]+c) } } bf } fn dijkstra(&self, s: usize) -> Vec<isize> { use std::collections::BinaryHeap; const INF: isize = std::isize::MAX; let mut dk: Vec<isize> = vec![INF; self.size]; dk[s] = 0; let mut pq = BinaryHeap::new(); pq.push((0,s)); while let Some((acc,v)) = pq.pop() { let acc = -acc; for &(w,c) in &self.adj[v] { let cand = acc + c; if cand < dk[w] { dk[w] = cand; pq.push((-cand,w)); } } } dk } fn warshall_floyd(&self) -> Vec<Vec<isize>> { const INF: isize = std::isize::MAX >> 1; let mut wf: Vec<Vec<isize>> = vec![vec![INF; self.size]; self.size]; for i in 0 .. self.size {wf[i][i] = 0} for (i, next) in self.adj.iter().enumerate() { for &(j, x) in next { wf[i][j] = x } } for k in 0 .. self.size { for i in 0 .. self.size { for j in 0 .. self.size { wf[i][j] = std::cmp::min(wf[i][j], wf[i][k] + wf[k][j]); } } } wf } fn coloring2(&self) -> Option<(Vec<usize>, Vec<usize>)> { fn paint(v: usize, p: bool, g: &Graph, cv: &mut Vec<Option<bool>>) -> bool { match cv[v] { None => { let next = &g.adj[v]; cv[v] = Some(p); next.iter().all(|&(w,_)|paint(w,!p,g,cv))}, Some(q) => {q == p} } } let mut canvas: Vec<Option<bool>> = vec![None; self.size]; let ans = paint(0, false, self, &mut canvas); let bs = canvas.iter().enumerate().filter(|&(_,&v)|v==Some(false)).map(|(i,_)|i).collect::<Vec<_>>(); let ws = canvas.iter().enumerate().filter(|&(_,&v)|v==Some(true)).map(|(i,_)|i).collect::<Vec<_>>(); if ans {Some((bs,ws))} else {None} } fn dfs(&self, s: usize) -> Vec<usize> { fn go(g: &Graph, current: usize, mut path: &mut Vec<usize>, mut visited: &mut Vec<bool>) { for &(next, _) in &g.adj[current] { if visited[next] { continue } else { visited[next] = true; path.push(next); go(&g, next, &mut path, &mut visited) } } } let mut path = vec![s]; let mut visited = vec![false; self.adj.len()]; visited[s] = true; go(&self, s, &mut path, &mut visited); path } fn cut(&mut self, v: usize, w: usize) { self.adj[v].retain(|&(t,_)| t != w); self.adj[w].retain(|&(t,_)| t != v); } } #[allow(dead_code)] mod get { use std::io::*; use std::str::*; pub fn val<T: FromStr>() -> T { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); buf.trim().parse::<T>().ok().unwrap() } pub fn vals<T: FromStr>(n: usize) -> Vec<T> { let mut vec: Vec<T> = vec![]; for _ in 0 .. n { vec.push(val()); } vec } pub fn tuple<T1: FromStr, T2: FromStr>() -> (T1, T2) { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); let mut it = buf.trim().split_whitespace(); let x = it.next().unwrap().parse::<T1>().ok().unwrap(); let y = it.next().unwrap().parse::<T2>().ok().unwrap(); (x, y) } pub fn tuples<T1: FromStr, T2: FromStr>(n: usize) -> Vec<(T1, T2)> { let mut vec: Vec<(T1, T2)> = vec![]; for _ in 0 .. n { vec.push(tuple()); } vec } pub fn tuple3<T1: FromStr, T2: FromStr, T3: FromStr>() -> (T1, T2, T3) { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); let mut it = buf.trim().split_whitespace(); let x = it.next().unwrap().parse::<T1>().ok().unwrap(); let y = it.next().unwrap().parse::<T2>().ok().unwrap(); let z = it.next().unwrap().parse::<T3>().ok().unwrap(); (x, y, z) } pub fn tuple3s<T1: FromStr, T2: FromStr, T3: FromStr>(n: usize) -> Vec<(T1, T2, T3)> { let mut vec: Vec<(T1, T2, T3)> = vec![]; for _ in 0 .. n { vec.push(tuple3()); } vec } pub fn list<T: FromStr>() -> Vec<T> { let mut buf = String::new(); stdin().read_line(&mut buf).ok(); buf.trim().split_whitespace().map(|t| t.parse::<T>().ok().unwrap()).collect() } pub fn lists<T: FromStr>(h: usize) -> Vec<Vec<T>> { let mut mat: Vec<Vec<T>> = vec![]; for _ in 0 .. h { mat.push(list()); } mat } }