AtCoderBeginnerContest225 D 問題 400 点 「Play Train」

問題リンク

問題概要

制約

解法

制約の最後を見ると，出力するノードの数は全部で$10^6$以下であることから，全部見に行っても TLE しないことがわかる。 クエリ 1,2 で各ノードの front/back を記録しておき，クエリ 3 では x の前後を追加していくことで連結成分をすべて取得することができる。

お気持ち

AC コード

#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
#![allow(dead_code)]
#![recursion_limit = "1024"]
use std::collections::{vec_deque, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::f64::consts::PI;
use std::mem::swap;
use std::ops::Index;

use itertools::{CombinationsWithReplacement, Itertools};
use num::{integer::Roots, traits::Pow, ToPrimitive};
use num_integer::{div_ceil, Integer};
use num_traits::{abs_sub, Float};
use permutohedron::Heap;
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::io::*;
use whiteread::parse_line;
//

fn solve() {
    #[rustfmt::skip]
    input! {
        N:usize, Q:usize
    }
    let mut front = vec![0; N + 1];
    let mut back = vec![0; N + 1];
    for _ in 0..Q {
        input! {
            q:usize
        }
        match q {
            1 => {
                input! {x:usize, y:usize}
                back[x] = y;
                front[y] = x;
            }
            2 => {
                input! {x: usize, y:usize}
                back[x] = 0;
                front[y] = 0;
            }
            3 => {
                input! {x:usize}
                let mut que = VecDeque::new();
                que.push_back(x);
                let mut now = x;
                while front[now] > 0 {
                    que.push_front(front[now] as usize);
                    now = front[now] as usize;
                }
                now = x;
                while back[now] > 0 {
                    que.push_back(back[now] as usize);
                    now = back[now] as usize;
                }
                println!("{} {}", que.len(), que.iter().join(" "));
            }
            _ => {}
        }
    }
}
fn main() {
    // input! {N:usize}
    // for _ in 0..N {
    //     solve();
    // }
    solve();
}