Submission #3011400


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();
    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 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 5287 Byte
Status RE
Exec Time 3159 ms
Memory 93120 KB

Compile Error

warning: constant item is never used: `DEBUG`, #[warn(dead_code)] on by default
 --> ./Main.rs:7:1
  |
7 | const DEBUG: bool = false;
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 2
WA × 1
AC × 1
WA × 5
TLE × 2
RE × 7
AC × 15
WA × 14
TLE × 4
RE × 15
Set Name Test Cases
Sample example_0.txt, example_1.txt, example_2.txt
Subtask1 bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_bubun_0.txt, random_bubun_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_bubun_0.txt, square_bubun_1.txt
All bone_0.txt, bone_1.txt, bone_2.txt, bone_bubun_0.txt, bone_bubun_1.txt, bone_bubun_2.txt, example_0.txt, example_1.txt, example_2.txt, handmade_0.txt, handmade_1.txt, handmade_2.txt, handmade_3.txt, komakai_0.txt, komakai_1.txt, komakai_2.txt, komakai_bubun_0.txt, komakai_bubun_1.txt, komakai_bubun_2.txt, maxrand_0.txt, maxrand_1.txt, maxrand_bubun_0.txt, maxrand_bubun_1.txt, random_0.txt, random_1.txt, random_bubun_0.txt, random_bubun_1.txt, renket_0.txt, renket_1.txt, smallrand_0.txt, smallrand_1.txt, smallrand_bubun_0.txt, smallrand_bubun_1.txt, smallrand_bubun_2.txt, square_0.txt, square_1.txt, square_bubun_0.txt, square_bubun_1.txt, supersmall_0.txt, supersmall_1.txt, threeren_0.txt, threeren_1.txt, treebase_0.txt, treebase_1.txt, treebase_2.txt, example_0.txt, example_1.txt, example_2.txt
Case Name Status Exec Time Memory
bone_0.txt WA 193 ms 72076 KB
bone_1.txt RE 181 ms 71932 KB
bone_2.txt WA 190 ms 71932 KB
bone_bubun_0.txt RE 39 ms 30972 KB
bone_bubun_1.txt AC 7 ms 10620 KB
bone_bubun_2.txt RE 55 ms 35068 KB
example_0.txt AC 3 ms 8444 KB
example_1.txt WA 3 ms 8572 KB
example_2.txt AC 3 ms 8572 KB
handmade_0.txt AC 3 ms 8572 KB
handmade_1.txt WA 3 ms 8572 KB
handmade_2.txt AC 3 ms 8572 KB
handmade_3.txt WA 3 ms 8572 KB
komakai_0.txt WA 268 ms 87732 KB
komakai_1.txt WA 264 ms 88180 KB
komakai_2.txt WA 269 ms 89872 KB
komakai_bubun_0.txt WA 258 ms 93120 KB
komakai_bubun_1.txt WA 253 ms 91028 KB
komakai_bubun_2.txt WA 251 ms 91028 KB
maxrand_0.txt AC 269 ms 84220 KB
maxrand_1.txt AC 269 ms 84220 KB
maxrand_bubun_0.txt RE 183 ms 69884 KB
maxrand_bubun_1.txt RE 183 ms 69884 KB
random_0.txt AC 9 ms 10620 KB
random_1.txt AC 144 ms 51452 KB
random_bubun_0.txt RE 8 ms 10492 KB
random_bubun_1.txt RE 47 ms 24828 KB
renket_0.txt RE 184 ms 67836 KB
renket_1.txt RE 185 ms 67836 KB
smallrand_0.txt AC 3 ms 8444 KB
smallrand_1.txt AC 3 ms 8572 KB
smallrand_bubun_0.txt WA 3 ms 8572 KB
smallrand_bubun_1.txt WA 3 ms 8572 KB
smallrand_bubun_2.txt RE 3 ms 8444 KB
square_0.txt TLE 3159 ms 53500 KB
square_1.txt TLE 3159 ms 53500 KB
square_bubun_0.txt TLE 3159 ms 53500 KB
square_bubun_1.txt TLE 3159 ms 47356 KB
supersmall_0.txt AC 3 ms 8444 KB
supersmall_1.txt AC 3 ms 8572 KB
threeren_0.txt RE 178 ms 63740 KB
threeren_1.txt RE 180 ms 65788 KB
treebase_0.txt RE 147 ms 57596 KB
treebase_1.txt RE 32 ms 18684 KB
treebase_2.txt RE 106 ms 43260 KB