結果
問題 | No.2914 正閉路検出 |
ユーザー |
|
提出日時 | 2024-10-05 06:19:22 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,734 bytes |
コンパイル時間 | 13,095 ms |
コンパイル使用メモリ | 398,876 KB |
実行使用メモリ | 45,912 KB |
最終ジャッジ日時 | 2024-10-05 06:19:41 |
合計ジャッジ時間 | 18,813 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 49 WA * 6 |
ソースコード
use proconio::{input, marker::Usize1};fn main() {match solve() {Some(closed_path) => {println!("{}\n{}\n{}",closed_path.edges.len(),closed_path.start + 1,closed_path.edges.iter().map(|edge_id| (edge_id + 1).to_string()).collect::<Vec<_>>().join(" "));}None => println!("-1"),}}fn solve() -> Option<ClonedPath> {input! {(n, m): (usize, usize),uvw: [(Usize1, Usize1, i64); m],}let mut graph = vec![vec![]; n];for (id, &(u, v, w)) in uvw.iter().enumerate() {let edge = Edge::new(id, u, v, w);graph[u].push(edge);graph[v].push(edge.inverse());}let create_increasing_closed_path =|path: &[usize], nodes: &[Option<Node>], start: usize, potential: i64| {let mut prev_path = vec![];let mut current = start;while current != 0 {let passed_edge = nodes[current].unwrap().passed_edge.unwrap();prev_path.push(passed_edge.id);current = passed_edge.from;}prev_path.reverse();let common_length = prev_path.iter().zip(path).take_while(|(node1, node2)| node1 == node2).count();let mut closed_path = prev_path[common_length..].iter().rev().chain(&path[common_length..]).cloned().collect::<Vec<_>>();if potential < nodes[start].unwrap().potential {closed_path.reverse();}closed_path};let mut nodes: Vec<Option<Node>> = vec![None; n];let mut stack: Vec<(Option<Edge>, i64, bool)> = vec![(None, 0, true)];let mut path: Vec<usize> = vec![];while let Some((passed_edge, potential, advance)) = stack.pop() {if !advance {path.pop().unwrap();continue;}if let Some(edge) = passed_edge {path.push(edge.id);}let current = passed_edge.map(|edge| edge.to).unwrap_or(0);if let Some(node) = nodes[current] {if potential != node.potential {let closed_path = create_increasing_closed_path(&path, &nodes, current, potential);return Some(ClonedPath {start: current,edges: closed_path,});}continue;}nodes[current] = Some(Node {potential,passed_edge,});stack.extend(graph[current].iter().flat_map(|&next_edge| {[(passed_edge, potential, false),(Some(next_edge), potential + next_edge.weight, true),]}));}None}#[allow(dead_code)]#[derive(Debug, Clone, Copy)]struct Edge {id: usize,from: usize,to: usize,weight: i64,}impl Edge {fn new(id: usize, from: usize, to: usize, weight: i64) -> Self {Self {id,from,to,weight,}}fn inverse(&self) -> Self {Self {id: self.id,from: self.to,to: self.from,weight: -self.weight,}}}#[derive(Debug, Clone, Copy)]struct Node {potential: i64,passed_edge: Option<Edge>,}#[derive(Debug, Clone)]struct ClonedPath {start: usize,edges: Vec<usize>,}