結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-24 02:14:55 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 525 ms / 2,000 ms |
コード長 | 7,100 bytes |
コンパイル時間 | 18,038 ms |
コンパイル使用メモリ | 378,752 KB |
実行使用メモリ | 41,820 KB |
最終ジャッジ日時 | 2024-06-25 02:26:36 |
合計ジャッジ時間 | 29,448 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
コンパイルメッセージ
warning: unused import: `std::cmp` --> src/main.rs:2:5 | 2 | use std::cmp; | ^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: unused import: `std::cmp::min` --> src/main.rs:3:5 | 3 | use std::cmp::min; | ^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeMap` --> src/main.rs:4:5 | 4 | use std::collections::BTreeMap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::process` --> src/main.rs:5:5 | 5 | use std::process; | ^^^^^^^^^^^^ warning: unused import: `std::collections::HashMap` --> src/main.rs:7:5 | 7 | use std::collections::HashMap; | ^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BTreeSet` --> src/main.rs:10:5 | 10 | use std::collections::BTreeSet; | ^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused import: `std::collections::BinaryHeap` --> src/main.rs:12:5 | 12 | use std::collections::BinaryHeap; | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ warning: unused imports: `Hash`, `Hasher` --> src/main.rs:13:17 | 13 | use std::hash::{Hash, Hasher}; | ^^^^ ^^^^^^ warning: unnecessary parentheses around `while` condition --> src/main.rs:140:10 | 140 | while(b>0){ | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 140 - while(b>0){ 140 + while b>0 { | warning: unnecessary parentheses around `while` condition --> src/main.rs:156:14 | 156 | while(n != 0){ | ^ ^ | help: remove these parentheses | 156 - while(n != 0){ 156 + while n != 0 { | warning: unnecessary parentheses around `if` condition --> src/main.rs:157:16 | 157 | if (n&1 == 1){ans = ans*x%MODu;} | ^ ^ | help: remove these parentheses | 157 - if (n&1 == 1){ans = ans*x%MODu;} 157 + if n&1 == 1 {ans = ans*x%MODu;} | warning: unnecessary p
ソースコード
use std::cmp::Ordering;use std::cmp;use std::cmp::min;use std::collections::BTreeMap;use std::process;use std::cmp::Ord;use std::collections::HashMap;use std::collections::HashSet;use std::collections::VecDeque;use std::collections::BTreeSet;use std::mem;use std::collections::BinaryHeap;use std::hash::{Hash, Hasher};pub struct Scanner<R> {stdin: R,}impl<R: std::io::Read> Scanner<R> {pub fn read<T: std::str::FromStr>(&mut self) -> T {use std::io::Read;let buf = self.stdin.by_ref().bytes().map(|b| b.unwrap()).skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r').take_while(|&b| b != b' ' && b != b'\n' && b != b'\r').collect::<Vec<_>>();std::str::from_utf8(&buf).unwrap().parse().ok().expect("Parse error.")}pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {(0..n).map(|_| self.read()).collect()}pub fn chars(&mut self) -> Vec<char> {self.read::<String>().chars().collect()}}pub trait BinarySearch<T> {fn lower_bound(&self, x:&T) -> usize;fn upper_bound(&self, x:&T) -> usize;}impl<T: Ord> BinarySearch<T> for VecDeque<T>{fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}impl<T: Ord> BinarySearch<T> for [T]{fn lower_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less => {low = mid + 1;}Ordering::Equal | Ordering::Greater => {high = mid;}}}low}fn upper_bound(&self, x: &T) -> usize {let mut low = 0;let mut high = self.len();while low != high {let mid = (low + high) / 2;match self[mid].cmp(x) {Ordering::Less | Ordering::Equal => {low = mid + 1;}Ordering::Greater => {high = mid;}}}low}}fn comb(a:usize, b:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{let mut a = a;let mut b = b;if a == 0 && b == 0{return 1;}if a<b || a<0{return 0;}let mut tmp = ifac[a-b]*ifac[b]%MODu;return tmp * fac[a]%MODu;}fn nHr(n:usize, r:usize, fac:&Vec<usize>, ifac:&Vec<usize>)->usize{return comb(n+r-1, r, fac, ifac);}fn modinv(a:usize, M:usize)->usize{let mut b = M as i64;let mut u = 1 as i64;let mut v = 0 as i64;let mut a = a as i64;let mut m = M as i64;while(b>0){let mut t = a/b;a -= t*b;mem::swap(&mut a, &mut b);u-=t*v;mem::swap(&mut u, &mut v);}u%=m;if u<0{u+=m;}return u as usize;}fn modpow(x:usize, n:usize) -> usize{let mut ans = 1;let mut n = n as usize;let mut x = x;while(n != 0){if (n&1 == 1){ans = ans*x%MODu;}x = x*x%MODu;n = n>>1;}ans}fn invs(max:usize)->(Vec<usize>, Vec<usize>){let mut fac = vec![0;max+1];let mut ifac = vec![0;max+1];fac[0] = 1;ifac[0] = 1;for i in 0..max{fac[i+1] = fac[i] * (i+1)%MODu;ifac[i+1] = ifac[i] * modpow(i+1, MODu - 2)%MODu;}(fac, ifac)}fn solve(){let sssss = std::io::stdin();let mut sc = Scanner { stdin: sssss.lock() };let mut N:usize = sc.read();let mut M:usize = sc.read();let mut g = vec![vec![];N];let mut g2 = g.clone();let mut h = vec![0usize;N];for i in 0..M{let mut u:usize = sc.read();let mut v:usize = sc.read();u-=1;v-=1;g[u].push(v);h[v]+=1;g2[u].push(v);g2[v].push(u);}let mut zeros = vec![];for i in 0..N{if h[i] == 0{zeros.push(i);}}fn dfs(s:usize,used:&mut Vec<bool>,vs:&mut HashSet<usize>,g:&Vec<Vec<usize>>){if used[s]{return;}used[s] = true;vs.insert(s);for i in &g[s]{dfs(*i, used, vs, g);}}let mut used = vec![false;N];let mut res= vec![];let mut u = HashSet::new();for i in 0..N{if used[i] == false{let mut vs = HashSet::new();dfs(i, &mut used, &mut vs, &g2);let mut vs:Vec<usize> = vs.into_iter().collect();let mut st = vec![];let mut tmp = vec![];for j in 0..vs.len(){if h[vs[j]] == 0{st.push(vs[j]);}}while(st.len() != 0){let mut i = st.pop().unwrap();tmp.push(i);for j in &g[i]{h[*j]-=1;if h[*j] == 0{st.push(*j);}}}let mut ok = true;for j in 0..vs.len(){if h[vs[j]] != 0{ok = false;}}if ok{for j in 0..tmp.len()-1{res.push(vec![tmp[j], tmp[j+1]]);}}else{for x in vs{u.insert(x);}}}}let mut u:Vec<usize> = u.into_iter().collect();for i in 0..u.len(){res.push(vec![u[i], u[(i+1)%u.len()]]);}println!("{}", res.len());for i in 0..res.len(){println!("{} {}", res[i][0]+1, res[i][1]+1);}}fn main(){solve();}const PI:f64 = std::f64::consts::PI;pub static MOD:i64 = 1000000007;pub static MODu:usize = 998244353;pub static MODi32:i32 = 1000000007;pub static eps:f64 = 1e-6;const INF: i64 = 1 << 60;const INFu:usize = 1<<56;const INFu128:u128 = 1<<126;