結果
問題 | No.2301 Namorientation |
ユーザー |
|
提出日時 | 2023-05-12 22:36:02 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 487 ms / 3,000 ms |
コード長 | 4,547 bytes |
コンパイル時間 | 14,174 ms |
コンパイル使用メモリ | 379,212 KB |
実行使用メモリ | 51,456 KB |
最終ジャッジ日時 | 2024-11-28 19:09:31 |
合計ジャッジ時間 | 28,881 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
pub mod scanner { pub struct Scanner { buf: Vec<String>, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next<T: std::str::FromStr>(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec<String> { source .split_whitespace() .rev() .map(String::from) .collect::<Vec<_>>() } } } pub mod directed_graph { type Weight = isize; #[derive(Clone)] pub struct Edge { pub from: usize, pub to: usize, pub index: usize, pub weight: Weight, } pub struct DirectedGraph { pub n: usize, pub m: usize, pub edges: Vec<Vec<Edge>>, pub orig_edges: Vec<Edge>, pub degree: Vec<usize>, } impl DirectedGraph { pub fn new(n: usize, m: usize) -> Self { let edges = vec![vec![]; n]; let orig_edges = vec![]; let degree = vec![0; n]; Self { n, m, edges, orig_edges, degree, } } pub fn init(scanner: &mut crate::scanner::Scanner, indexed: usize) -> Self { let n: usize = scanner.next(); let m: usize = n; let mut graph = Self::new(n, m); for index in 0..m { let from: usize = scanner.next::<usize>() - indexed; let to: usize = scanner.next::<usize>() - indexed; let weight: Weight = 1; graph.orig_edges.push(Edge { from, to, index, weight, }); graph.add_edge(from, to, index, weight); graph.add_edge(to, from, index, weight); graph.degree[from] += 1; graph.degree[to] += 1; } graph } pub fn add_edge(&mut self, from: usize, to: usize, index: usize, weight: Weight) { let edge = Edge { from, to, index, weight, }; self.edges[from].push(edge); } } } use crate::{directed_graph::DirectedGraph, scanner::Scanner}; fn main() { let mut scanner = Scanner::new(); let t: usize = 1; for _ in 0..t { solve(&mut scanner); } } fn solve(scanner: &mut Scanner) { let mut graph = DirectedGraph::init(scanner, 1); let n = graph.n; let mut dir = vec![!0; n]; let mut que = std::collections::VecDeque::new(); for u in 0..n { if graph.degree[u] == 1 { que.push_back(u); } } while let Some(u) = que.pop_front() { for edge in graph.edges[u].iter_mut() { if dir[edge.index] == !0 { dir[edge.index] = u; graph.degree[edge.from] -= 1; graph.degree[edge.to] -= 1; if graph.degree[edge.to] == 1 { que.push_back(edge.to); } } } } let mut cur = 0; for u in 0..n { if graph.degree[u] == 2 { cur = u; break; } } loop { let mut updated = false; for edge in graph.edges[cur].iter_mut() { if graph.degree[edge.to] == 2 { dir[edge.index] = cur; graph.degree[edge.from] -= 1; graph.degree[edge.to] -= 1; cur = edge.to; updated = true; break; } } if !updated { break; } } for edge in graph.edges[cur].iter_mut() { if dir[edge.index] == !0 { dir[edge.index] = cur; break; } } for i in 0..n { if dir[i] == graph.orig_edges[i].from { println!("->"); } else { println!("<-"); } } }