Submission #3011399
Source Code Expand
#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::{Read, Write, BufWriter}; const DEBUG: bool = false; #[allow(dead_code)] fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).ok().unwrap(); ret } fn get_word() -> String { let mut stdin = std::io::stdin(); let mut u8b: [u8; 1] = [0]; loop { let mut buf: Vec<u8> = Vec::with_capacity(16); loop { let res = stdin.read(&mut u8b); if res.unwrap_or(0) == 0 || u8b[0] <= b' ' { break; } else { buf.push(u8b[0]); } } if buf.len() >= 1 { let ret = String::from_utf8(buf).unwrap(); return ret; } } } #[allow(dead_code)] fn get<T: std::str::FromStr>() -> T { get_word().parse().ok().unwrap() } const INF: usize = 1 << 28; fn dfs(v: usize, par: usize, g: &[Vec<(usize, usize)>], ord: &mut [usize], low: &mut [usize], k: &mut usize, bridges: &mut Vec<usize>) { ord[v] = *k; low[v] = *k; *k += 1; for &(w, eidx) in g[v].iter() { if par == w { continue; } if ord[w] < ord[v] { low[v] = min(low[v], ord[w]); } else { dfs(w, v, g, ord, low, k, bridges); low[v] = min(low[v], low[w]); if ord[v] < low[w] { bridges.push(eidx); } } } } fn dfs_comp(v: usize, g: &[Vec<(usize, usize)>], ord: &[usize], low: &[usize], cur_becomp: usize, becomp_count: &mut usize, becomp: &mut [usize], tree: &mut [Vec<(usize, usize)>]) { becomp[v] = cur_becomp; for &(w, eidx) in g[v].iter() { if ord[w] > ord[v] { if ord[v] < low[w] { *becomp_count += 1; tree[cur_becomp].push((*becomp_count, eidx)); dfs_comp(w, g, ord, low, *becomp_count, becomp_count, becomp, tree); } else { dfs_comp(w, g, ord, low, cur_becomp, becomp_count, becomp, tree); } } } } fn dfs_count(v: usize, tree: &[Vec<(usize, usize)>], tvis: &mut [bool], conn: &[usize], even_edges: &mut HashSet<usize>, cur_comp: usize, comp: &mut [usize]) -> usize { tvis[v] = true; comp[v] = cur_comp; let mut cnt = conn[v]; for &(w, eidx) in tree[v].iter() { let sub = dfs_count(w, tree, tvis, conn, even_edges, cur_comp, comp); if sub % 2 == 0 { even_edges.insert(eidx); } cnt += sub + 1; } cnt } fn solve() { let out = std::io::stdout(); let mut out = BufWriter::new(out.lock()); macro_rules! puts { ($format:expr) => (write!(out,$format).unwrap()); ($format:expr, $($args:expr),+) => (write!(out,$format,$($args),*).unwrap()) } let n: usize = get(); let m = 2 * n + 1; let mut x = vec![0; m]; let mut y = vec![0; m]; for i in 0 .. m { x[i] = get::<usize>() - 1; y[i] = get::<usize>() - 1; } let n_vert = 2 * m; let mut g = vec![Vec::new(); n_vert]; for i in 0 .. m { g[x[i]].push((m + y[i], i)); g[m + y[i]].push((x[i], i)); } let mut ord = vec![INF; n_vert]; let mut low = vec![INF; n_vert]; let mut k = 0; let mut becomp_count = 0; let mut becomp = vec![INF; n_vert]; let mut bridges = Vec::new(); // rooted forest let mut tree = vec![Vec::new(); n_vert]; for i in 0 .. n_vert { if ord[i] == INF { dfs(i, n_vert, &g, &mut ord, &mut low, &mut k, &mut bridges); dfs_comp(i, &g, &ord, &low, becomp_count, &mut becomp_count, &mut becomp, &mut tree); becomp_count += 1; } } tree = tree[..becomp_count].to_vec(); if DEBUG { eprintln!("low = {:?}, ord = {:?}", low, ord); eprintln!("becomp = {:?}", becomp); eprintln!("bridge = {:?}", bridges); } let mut conn = vec![0; becomp_count]; for i in 0 .. m { if becomp[x[i]] == becomp[m + y[i]] { conn[becomp[x[i]]] += 1; } } let mut ans = vec![false; m]; // odd components let mut tvis = vec![false; becomp_count]; let mut odd_comps = Vec::new(); let mut even_edges = HashSet::new(); let mut comp = vec![0; becomp_count]; let mut comp_count = 0; for i in 0 .. becomp_count { if !tvis[i] { let s = dfs_count(i, &tree, &mut tvis, &conn, &mut even_edges, comp_count, &mut comp); if s % 2 == 1 { odd_comps.push(comp_count); } comp_count += 1; } } if DEBUG { eprintln!("conn = {:?}", conn); eprintln!("odd_comps = {:?}", odd_comps); eprintln!("even_edges = {:?}", even_edges); } if odd_comps.len() == 1 { let odd_comp = odd_comps[0]; for i in 0 .. m { if comp[becomp[x[i]]] == odd_comp { ans[i] = true; } } for b in bridges { if comp[becomp[b]] == odd_comp { ans[b] = even_edges.contains(&b); } } } for i in 0 .. m { puts!("{}\n", if ans[i] { "OK" } else { "NG" }); } } 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(); } // I know this code is wrong.
Submission Info
Submission Time | |
---|---|
Task | D - みんな仲良し高橋君 |
User | kobae964 |
Language | Rust (1.15.1) |
Score | 0 |
Code Size | 5615 Byte |
Status | CE |
Compile Error
error: macro undefined: 'eprintln!' --> ./Main.rs:133:9 | 133 | eprintln!("low = {:?}, ord = {:?}", low, ord); | ^^^^^^^^ | = help: did you mean `println!`? error: macro undefined: 'eprintln!' --> ./Main.rs:134:9 | 134 | eprintln!("becomp = {:?}", becomp); | ^^^^^^^^ | = help: did you mean `println!`? error: macro undefined: 'eprintln!' --> ./Main.rs:135:9 | 135 | eprintln!("bridge = {:?}", bridges); | ^^^^^^^^ | = help: did you mean `println!`? error: macro undefined: 'eprintln!' --> ./Main.rs:160:9 | 160 | eprintln!("conn = {:?}", conn); | ^^^^^^^^ | = help: did you mean `println!`? error: macro undefined: 'eprintln!' --> ./Main.rs:161:9 | 161 | eprintln!("odd_comps = {:?}", odd_comps); | ^^^^^^^^ | = help: did you mean `println!`? error: macro undefined: 'eprintln!' --> ./Main.rs:162:9 | 162 | eprintln!("even_edges...