結果

問題 No.1477 Lamps on Graph
ユーザー kichi2004_kichi2004_
提出日時 2021-04-16 20:08:53
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 2,708 bytes
コンパイル時間 14,831 ms
コンパイル使用メモリ 379,164 KB
実行使用メモリ 17,388 KB
最終ジャッジ日時 2024-07-02 22:00:51
合計ジャッジ時間 20,078 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 38
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused imports: `BTreeMap`, `BTreeSet`, `BinaryHeap`, `HashMap`
 --> src/main.rs:3:34
  |
3 | use std::collections::{VecDeque, HashMap, BTreeSet, BinaryHeap, BTreeMap};
  |                                  ^^^^^^^  ^^^^^^^^  ^^^^^^^^^^  ^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::convert::TryFrom`
 --> src/main.rs:4:5
  |
4 | use std::convert::TryFrom;
  |     ^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::cmp::min`
 --> src/main.rs:5:5
  |
5 | use std::cmp::min;
  |     ^^^^^^^^^^^^^

warning: constant `MOD` is never used
 --> src/main.rs:7:7
  |
7 | const MOD: usize = 998244353;
  |       ^^^
  |
  = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use std::str::FromStr;
use std::io::{BufRead, stdin, Stdin};
use std::collections::{VecDeque, HashMap, BTreeSet, BinaryHeap, BTreeMap};
use std::convert::TryFrom;
use std::cmp::min;

const MOD: usize = 998244353;

fn main() {
    let mut sc = Scanner::new();

    let n = sc.read_usize();
    let m = sc.read_usize();
    let a = sc.read_vec::<i32>(n);
    let mut graph = (0..n).map(|_| Vec::<usize>::new()).collect::<Vec<_>>();
    for _ in 0..m {
        let a = sc.read_usize();
        let b = sc.read_usize();
        graph[a-1].push(b-1);
        graph[b-1].push(a-1);
    }

    let mut is_on = vec![false; n];
    let k = sc.read_usize();
    for _ in 0..k {
        let b = sc.read_usize();
        is_on[b - 1] = true;
    }

    let mut list = (0..n).map(|i| (a[i], i)).collect::<Vec<_>>();
    list.sort();
    let mut ans = Vec::<usize>::new();
    for (_, i) in list{
        if !is_on[i] {
            continue;
        }
        is_on[i] = false;
        ans.push(i + 1);
        for j in &graph[i] {
            if a[i] < a[*j] {
                is_on[*j] = !is_on[*j];
            }
        }
    }

    if is_on.iter().any(|s| *s) {
        println!("-1");
        return;
    }
    println!("{}", ans.len());
    for v in ans {
        println!("{}", v);
    }
}

struct Scanner {
    sep: char,
    inputs: VecDeque<String>,
    cin: Stdin,
}

#[allow(unused)]
impl Scanner {
    pub fn new() -> Scanner {
        Self::from_sep(' ')
    }
    pub fn from_sep(ch: char) -> Scanner {
        Scanner {
            sep: ch,
            inputs: VecDeque::new(),
            cin: stdin(),
        }
    }
    pub fn read<T: FromStr>(&mut self) -> T {
        let mut tries = 0;

        let cin_base = &mut self.cin;
        let cin = &mut cin_base.lock();

        while self.inputs.is_empty() {
            if tries == 3 {
                panic!("3 Blank lines found.");
            }

            let mut str: String = String::new();
            cin.read_line(&mut str).unwrap();
            for s in str.trim_end().split(self.sep) {
                &self.inputs.push_back(String::from(s));
            }
            tries += 1;
        }
        let s: String = String::from(&self.inputs.pop_front().unwrap());
        s.parse::<T>().ok()
            .expect("Failed to parse token.")
    }
    pub fn read_i32(&mut self) -> i32 { self.read() }
    pub fn read_i64(&mut self) -> i64 { self.read() }
    pub fn read_usize(&mut self) -> usize { self.read() }
    pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect::<Vec<_>>()
    }
    pub fn read_chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect::<Vec<_>>() }
}
0