結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2020-10-09 23:46:41 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 3,865 bytes |
コンパイル時間 | 13,477 ms |
コンパイル使用メモリ | 377,596 KB |
実行使用メモリ | 33,024 KB |
最終ジャッジ日時 | 2024-07-20 14:37:22 |
合計ジャッジ時間 | 23,491 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#![allow(unused_imports)] use {std::cmp::*, std::collections::*, std::io::Write, std::ops::*}; #[allow(unused_macros)] macro_rules !dbg {($($e :expr ) ,*) =>{#[cfg (debug_assertions ) ] $({let (e ,mut err ) =(stringify !($e ) ,std ::io ::stderr () ) ;writeln !(err ,"{} = {:?}" ,e ,$e ) .unwrap () } ) *} ;} #[allow(unused_macros)] macro_rules !min {($a :expr $(,) *) =>{{$a } } ;($a :expr ,$b :expr $(,) *) =>{{std ::cmp ::min ($a ,$b ) } } ;($a :expr ,$($rest :expr ) ,+$(,) *) =>{{std ::cmp ::min ($a ,min !($($rest ) ,+) ) } } ;} #[allow(unused_macros)] macro_rules !chmin {($base :expr ,$($cmps :expr ) ,+$(,) *) =>{{let cmp_min =min !($($cmps ) ,+) ;if $base >cmp_min {$base =cmp_min ;true } else {false } } } ;} #[allow(unused_macros)] macro_rules !max {($a :expr $(,) *) =>{{$a } } ;($a :expr ,$b :expr $(,) *) =>{{std ::cmp ::max ($a ,$b ) } } ;($a :expr ,$($rest :expr ) ,+$(,) *) =>{{std ::cmp ::max ($a ,max !($($rest ) ,+) ) } } ;} #[allow(unused_macros)] macro_rules !chmax {($base :expr ,$($cmps :expr ) ,+$(,) *) =>{{let cmp_max =max !($($cmps ) ,+) ;if $base <cmp_max {$base =cmp_max ;true } else {false } } } ;} #[allow(dead_code)] mod scanner { use std; use std::io::Read; use std::str::FromStr; use std::str::SplitWhitespace; pub struct Scanner<'a> { it: SplitWhitespace<'a>, } impl<'a> Scanner<'a> { pub fn new(s: &'a String) -> Scanner<'a> { Scanner { it: s.split_whitespace(), } } pub fn next<T: FromStr>(&mut self) -> T { match self.it.next().unwrap().parse::<T>() { Ok(v) => v, _ => panic!("Scanner error"), } } pub fn next_chars(&mut self) -> Vec<char> { self.next::<String>().chars().collect() } pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> { (0..len).map(|_| self.next()).collect() } } pub fn read_string() -> String { let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s } } fn main() { let sc = scanner::read_string(); let mut sc = scanner::Scanner::new(&sc); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let n: usize = sc.next(); let mut map = std::collections::BTreeMap::<(usize, usize), usize>::new(); let mut to = vec![vec![]; n]; for i in 0..n { let a = sc.next::<usize>() - 1; let b = sc.next::<usize>() - 1; to[a].push(b); to[b].push(a); map.insert((a, b), i); map.insert((b, a), i); } let mut stack = vec![]; let mut node = vec![]; let mut set = std::collections::BTreeSet::<usize>::new(); dfs(0, 0, &to, &mut set, &mut stack, &mut node); let mut ans = vec![]; for a in node.windows(2) { ans.push(map.get(&(a[0], a[1])).unwrap()); } ans.push(map.get(&(node[0], node[node.len() - 1])).unwrap()); writeln!(out, "{}", ans.len()).unwrap(); for i in 0..ans.len() { if i != 0 { write!(out, " ").unwrap(); } write!(out, "{}", ans[i] + 1).unwrap(); } writeln!(out, "").unwrap(); } fn dfs( u: usize, p: usize, to: &Vec<Vec<usize>>, set: &mut BTreeSet<usize>, stack: &mut Vec<usize>, ans: &mut Vec<usize>, ) -> bool { stack.push(u); set.insert(u); for &v in to[u].iter() { if v == p { continue; } if set.contains(&v) { while let Some(x) = stack.pop() { ans.push(x); if x == v { break; } } return true; } if dfs(v, u, to, set, stack, ans) { return true; } } stack.pop(); set.remove(&u); false }