結果

問題 No.1436 Rgaph
ユーザー akakimidoriakakimidori
提出日時 2021-03-19 23:09:18
言語 Rust
(1.77.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,350 bytes
コンパイル時間 1,931 ms
コンパイル使用メモリ 158,604 KB
実行使用メモリ 8,752 KB
最終ジャッジ日時 2023-08-12 05:40:11
合計ジャッジ時間 9,352 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
8,752 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 20 ms
4,376 KB
testcase_07 AC 1 ms
4,384 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 16 ms
4,376 KB
testcase_11 AC 30 ms
4,384 KB
testcase_12 AC 23 ms
4,376 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1,131 ms
4,376 KB
testcase_15 AC 221 ms
4,384 KB
testcase_16 AC 332 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,384 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 5 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 3 ms
4,384 KB
testcase_25 AC 31 ms
4,380 KB
testcase_26 AC 21 ms
4,380 KB
testcase_27 AC 20 ms
4,380 KB
testcase_28 AC 1 ms
4,508 KB
testcase_29 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin SCC ----------
pub struct SCC {
    size: usize,
    edge: Vec<(u32, u32)>,
}

impl SCC {
    pub fn new(size: usize) -> Self {
        assert!(size <= 10usize.pow(8));
        SCC { size, edge: vec![] }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        assert!(a < self.size && b < self.size);
        self.edge.push((a as u32, b as u32));
    }
    pub fn build(&self) -> (usize, Vec<usize>) {
        let size = self.size;
        let mut start = vec![0u32; size + 1];
        self.edge.iter().for_each(|e| start[e.0 as usize + 1] += 1);
        for i in 1..=size {
            start[i] += start[i - 1];
        }
        let mut buf = vec![0; self.edge.len()];
        for &(a, b) in self.edge.iter() {
            let po = &mut start[a as usize];
            buf[*po as usize] = b;
            *po += 1;
        }
        let mut s = 0usize;
        let mut neighbor = start
            .into_iter()
            .take(size)
            .map(|t| {
                let t = t as usize;
                let it = buf[s..t].iter().map(|p| *p as usize);
                s = t;
                it
            })
            .collect::<Vec<_>>();
        let mut ord = vec![size; size];
        let mut assigned = vec![false; size];
        let mut stack_s = vec![];
        let mut stack_p = vec![];
        let mut call = vec![];
        let mut now_ord = 0;
        let mut res = vec![0; size];
        let mut id = 0;
        enum Operation {
            Call(usize),
            Iter(usize),
            Eval(usize),
        }
        for i in 0..size {
            if ord[i] != size {
                continue;
            }
            call.push(Operation::Call(i));
            while let Some(op) = call.pop() {
                match op {
                    Operation::Call(v) => {
                        ord[v] = now_ord;
                        now_ord += 1;
                        stack_s.push(v);
                        stack_p.push(v);
                        call.push(Operation::Eval(v));
                        call.push(Operation::Iter(v));
                    }
                    Operation::Iter(v) => {
                        let it = &mut neighbor[v];
                        while let Some(u) = it.next() {
                            if ord[u] == size {
                                call.push(Operation::Iter(v));
                                call.push(Operation::Call(u));
                                break;
                            } else if !assigned[u] {
                                while ord[*stack_p.last().unwrap()] > ord[u] {
                                    stack_p.pop();
                                }
                            }
                        }
                    }
                    Operation::Eval(v) => {
                        if *stack_p.last().unwrap() == v {
                            while let Some(u) = stack_s.pop() {
                                res[u] = id;
                                assigned[u] = true;
                                if u == v {
                                    break;
                                }
                            }
                            stack_p.pop();
                            id += 1;
                        }
                    }
                }
            }
        }
        res.iter_mut().for_each(|v| *v = id - 1 - *v);
        (id, res)
    }
}
// ---------- end SCC ----------
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------

fn dfs(
    v: usize,
    g: &[Vec<(usize, usize)>],
    depth: &mut [usize],
    used: &mut [bool],
    state: &mut [usize],
    parent: &mut [(usize, usize)],
) {
    used[v] = true;
    let d = depth[v] + 1;
    for &(u, k) in g[v].iter() {
        if used[u] && depth[u] < depth[v] {
            state[k] = 2;
        } else {
            parent[u] = (v, k);
            depth[u] = d;
            state[k] = d & 1;
            dfs(u, g, depth, used, state, parent);
        }
    }
}

fn run() {
    input! {
        n: usize,
        m: usize,
        e: [(usize1, usize1); m],
    }
    let mut scc = SCC::new(n);
    let mut g = vec![vec![]; n];
    for (i, &(a, b)) in e.iter().enumerate() {
        scc.add_edge(a, b);
        g[a].push((b, i));
    }
    if scc.build().0 > 1 {
        println!("-1");
        return;
    }
    for root in 0..n {
        let mut depth = vec![0; n];
        let mut used = vec![false; n];
        let mut state = vec![2; m];
        let mut parent = vec![(n, m); n];
        dfs(root, &g, &mut depth, &mut used, &mut state, &mut parent);
        let mut back = vec![];
        for (i, state) in state.iter().enumerate() {
            if *state == 2 {
                let (s, t) = e[i];
                back.push((s, t, i));
            }
        }
        let cnt = state.iter().filter(|p| **p == 2).count() > 1;
        let elem = back
            .iter()
            .any(|&(s, t, _)| (depth[s] - depth[t] + 1) % 2 == 1);
        if !(cnt && elem) {
            continue;
        }
        let mut elem = [false; 2];
        for &(s, t, k) in back.iter() {
            if (depth[s] - depth[t] + 1) % 2 == 1 {
                continue;
            }
            if depth[t] % 2 == 0 {
                state[k] = 1;
                elem[1] = true;
            } else {
                state[k] = 0;
                elem[0] = true;
            }
        }
        for &(s, t, k) in back.iter() {
            if (depth[s] - depth[t] + 1) % 2 == 0 {
                continue;
            }
            let x = elem.iter().position(|p| !*p).unwrap_or(0);
            state[k] = x;
            elem[x] = true;
        }
        let mut ans = String::new();
        for state in state {
            if state == 0 {
                ans.push('R');
            } else {
                ans.push('G');
            }
        }
        println!("{}", ans);
        return;
    }
    println!("-1");
}

fn main() {
    run();
}
0