結果
問題 | No.3031 曲面の向き付け |
ユーザー |
![]() |
提出日時 | 2025-02-21 22:32:39 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 296 ms / 2,000 ms |
コード長 | 4,837 bytes |
コンパイル時間 | 14,030 ms |
コンパイル使用メモリ | 398,388 KB |
実行使用メモリ | 46,444 KB |
最終ジャッジ日時 | 2025-02-21 22:33:07 |
合計ジャッジ時間 | 20,538 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
コンパイルメッセージ
warning: variable does not need to be mutable --> src/main.rs:111:9 | 111 | let mut vec: Vec<i64> = read_vec(); | ----^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: variable does not need to be mutable --> src/main.rs:117:9 | 117 | let mut vec: Vec<i64> = read_vec(); | ----^^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/main.rs:122:9 | 122 | let mut vec: Vec<usize> = read_vec(); | ----^^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/main.rs:128:9 | 128 | let mut vec: Vec<f64> = read_vec(); | ----^^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/main.rs:133:9 | 133 | let mut vec: Vec<char> = read_vec(); | ----^^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/main.rs:138:9 | 138 | let mut vec: Vec<usize> = read_vec(); | ----^^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/main.rs:143:9 | 143 | let mut vec: Vec<i64> = read_vec(); | ----^^^ | | | help: remove this `mut` warning: variable does not need to be mutable --> src/main.rs:149:9 | 149 | let mut vec: Vec<usize> = read_vec(); | ----^^^ | | | help: remove this `mut`
ソースコード
#![allow(dead_code)] #![allow(unused_imports)] #![allow(unused_macros)] use std::cmp::*; use std::fmt::*; use std::hash::*; use std::io::BufRead; use std::iter::FromIterator; use std::*; use std::{cmp, collections, fmt, io, iter, ops, str}; const INF: i64 = 1223372036854775807; const UINF: usize = INF as usize; const LINF: i64 = 2147483647; const INF128: i128 = 1223372036854775807000000000000; const MOD1: i64 = 1000000007; const MOD9: i64 = 998244353; const MOD: i64 = MOD9; const UMOD: usize = MOD as usize; const M_PI: f64 = 3.14159265358979323846; use cmp::Ordering::*; use std::collections::*; use std::io::stdin; use std::io::stdout; use std::io::Write; macro_rules! p { ($x:expr) => { println!("{}", $x); }; } macro_rules! vp { ($x:expr) => { println!( "{}", $x.iter() .map(|x| x.to_string()) .collect::<Vec<_>>() .join(" ") ); }; } macro_rules! d { ($x:expr) => { eprintln!("{:?}", $x); }; } macro_rules! yn { ($val:expr) => { if $val { println!("Yes"); } else { println!("No"); } }; } macro_rules! map{ ($($key:expr => $val:expr),*) => { { let mut map = ::std::collections::BTreeMap::new(); $( map.insert($key, $val); )* map } }; } macro_rules! set{ ($($key:expr),*) => { { let mut set = ::std::collections::BTreeSet::new(); $( set.insert($key); )* set } }; } #[allow(dead_code)] fn read<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } #[allow(dead_code)] fn read_mat<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> { (0..n).map(|_| read_vec()).collect() } #[allow(dead_code)] fn readii() -> (i64, i64) { let mut vec: Vec<i64> = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readiii() -> (i64, i64, i64) { let mut vec: Vec<i64> = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readuu() -> (usize, usize) { let mut vec: Vec<usize> = read_vec(); (vec[0], vec[1]) } #[allow(dead_code)] fn readff() -> (f64, f64) { let mut vec: Vec<f64> = read_vec(); (vec[0], vec[1]) } fn readcc() -> (char, char) { let mut vec: Vec<char> = read_vec(); (vec[0], vec[1]) } fn readuuu() -> (usize, usize, usize) { let mut vec: Vec<usize> = read_vec(); (vec[0], vec[1], vec[2]) } #[allow(dead_code)] fn readiiii() -> (i64, i64, i64, i64) { let mut vec: Vec<i64> = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } #[allow(dead_code)] fn readuuuu() -> (usize, usize, usize, usize) { let mut vec: Vec<usize> = read_vec(); (vec[0], vec[1], vec[2], vec[3]) } //derive clone #[derive(Clone)] struct E { to: usize, p: u8, } fn main() { let m: usize = read(); let mut t = vec![]; for _ in 0..m { let v: Vec<u32> = read_vec(); t.push((v[0], v[1], v[2])); } let mut e = HashMap::new(); for (i, &(a, b, c)) in t.iter().enumerate() { let edges = vec![((a, b), 0u8), ((a, c), 1u8), ((b, c), 0u8)]; for ((u, v), f) in edges { e.entry((u, v)).or_insert(vec![]).push((i, f)); } } let mut g = vec![vec![]; m]; for (_, v) in e { if v.len() > 2 { p!("NO"); return; } if v.len() == 2 { let (t1, f1) = v[0]; let (t2, f2) = v[1]; let p = 1 ^ (f1 ^ f2); g[t1].push(E { to: t2, p }); g[t2].push(E { to: t1, p }); } } let mut c = vec![None; m]; //0の渦の隣には1が隣接してなければならない三角形を単位にして二部グラフ判定をする。 for i in 0..m { if c[i].is_none() { let mut q = VecDeque::new(); c[i] = Some(0); q.push_back(i); while let Some(u) = q.pop_front() { let cu = c[u].unwrap(); for e in &g[u] { let v = e.to; let r = cu ^ e.p; if let Some(cv) = c[v] { if cv != r { p!("NO"); return; } } else { c[v] = Some(r); q.push_back(v); } } } } } p!("YES"); }