https://atcoder.jp/contests/abc327/tasks/abc327_d
とをエッジと考えてグラフを作り、0の隣を1として矛盾が無いか調べます。
// Good Tuple Problem #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } fn YesNo(b: bool) -> String { return (if b { "Yes" } else { "No" }).to_string() } //////////////////// Graph //////////////////// type Node = usize; type Graph = Vec<Vec<Node>>; fn make_graph(N: usize, A: Vec<usize>, B: Vec<usize>) -> Option<Graph> { let mut graph: Graph = vec![vec![]; N]; for (&u, &v) in A.iter().zip(B.iter()) { if u == v { return None } graph[u].push(v); graph[v].push(u) } Some(graph) } //////////////////// process //////////////////// fn read_input() -> (usize, Vec<Node>, Vec<Node>) { let v = read_vec(); let N = v[0]; let A: Vec<Node> = read_vec::<Node>().into_iter().map(|e| e-1).collect(); let B: Vec<Node> = read_vec::<Node>().into_iter().map(|e| e-1).collect(); (N, A, B) } fn F(N: usize, A: Vec<usize>, B: Vec<usize>) -> bool { let op = make_graph(N, A, B); if op.is_none() { return false } let graph = op.unwrap(); let mut X: Vec<i32> = vec![-1; N]; for u in 0..N { if X[u] != -1 { continue } let mut stack: Vec<Node> = vec![u]; X[u] = 0; while let Some(v) = stack.pop() { for &w in graph[v].iter() { if X[w] == X[v] { return false } else if X[w] == -1 { X[w] = 1 - X[v]; stack.push(w) } } } } true } fn main() { let (N, A, B) = read_input(); println!("{}", YesNo(F(N, A, B))) }