結果

問題 No.1553 Lovely City
ユーザー Vwxyz32795915Vwxyz32795915
提出日時 2021-06-24 02:14:55
言語 Rust
(1.77.0)
結果
AC  
実行時間 565 ms / 2,000 ms
コード長 7,100 bytes
コンパイル時間 4,037 ms
コンパイル使用メモリ 171,116 KB
実行使用メモリ 43,984 KB
最終ジャッジ日時 2023-09-07 08:04:19
合計ジャッジ時間 18,721 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,352 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 44 ms
13,148 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 2 ms
4,388 KB
testcase_08 AC 330 ms
28,956 KB
testcase_09 AC 381 ms
31,080 KB
testcase_10 AC 408 ms
33,776 KB
testcase_11 AC 296 ms
24,748 KB
testcase_12 AC 425 ms
34,356 KB
testcase_13 AC 315 ms
26,400 KB
testcase_14 AC 353 ms
28,980 KB
testcase_15 AC 329 ms
26,900 KB
testcase_16 AC 412 ms
32,464 KB
testcase_17 AC 297 ms
26,064 KB
testcase_18 AC 555 ms
42,448 KB
testcase_19 AC 561 ms
42,544 KB
testcase_20 AC 563 ms
42,528 KB
testcase_21 AC 565 ms
43,760 KB
testcase_22 AC 565 ms
42,364 KB
testcase_23 AC 561 ms
42,424 KB
testcase_24 AC 563 ms
42,468 KB
testcase_25 AC 559 ms
43,980 KB
testcase_26 AC 561 ms
42,428 KB
testcase_27 AC 557 ms
43,984 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `std::cmp`
 --> Main.rs:2:5
  |
2 | use std::cmp;
  |     ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::cmp::min`
 --> Main.rs:3:5
  |
3 | use std::cmp::min;
  |     ^^^^^^^^^^^^^

warning: unused import: `std::collections::BTreeMap`
 --> Main.rs:4:5
  |
4 | use std::collections::BTreeMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::process`
 --> Main.rs:5:5
  |
5 | use std::process;
  |     ^^^^^^^^^^^^

warning: unused import: `std::collections::HashMap`
 --> Main.rs:7:5
  |
7 | use std::collections::HashMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::collections::BTreeSet`
  --> Main.rs:10:5
   |
10 | use std::collections::BTreeSet;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::collections::BinaryHeap`
  --> Main.rs:12:5
   |
12 | use std::collections::BinaryHeap;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused imports: `Hash`, `Hasher`
  --> Main.rs:13:17
   |
13 | use std::hash::{Hash, Hasher};
   |                 ^^^^  ^^^^^^

warning: unnecessary parentheses around `while` condition
   --> 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
   --> 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
   --> 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 parentheses around `while` condition
   --> M

ソースコード

diff # 

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;
0