結果

問題 No.1477 Lamps on Graph
ユーザー kichi2004_kichi2004_
提出日時 2021-04-16 20:08:53
言語 Rust
(1.77.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 87 ms
8,608 KB
testcase_13 AC 92 ms
8,540 KB
testcase_14 AC 115 ms
9,268 KB
testcase_15 AC 42 ms
5,376 KB
testcase_16 AC 31 ms
6,404 KB
testcase_17 AC 33 ms
5,376 KB
testcase_18 AC 139 ms
12,032 KB
testcase_19 AC 87 ms
8,664 KB
testcase_20 AC 28 ms
5,376 KB
testcase_21 AC 120 ms
10,928 KB
testcase_22 AC 15 ms
5,376 KB
testcase_23 AC 53 ms
6,016 KB
testcase_24 AC 137 ms
10,760 KB
testcase_25 AC 37 ms
5,376 KB
testcase_26 AC 130 ms
12,192 KB
testcase_27 AC 46 ms
5,880 KB
testcase_28 AC 65 ms
8,192 KB
testcase_29 AC 67 ms
6,324 KB
testcase_30 AC 78 ms
6,992 KB
testcase_31 AC 47 ms
6,348 KB
testcase_32 AC 214 ms
17,000 KB
testcase_33 AC 167 ms
17,388 KB
testcase_34 AC 190 ms
17,260 KB
testcase_35 AC 189 ms
15,208 KB
testcase_36 AC 182 ms
15,472 KB
testcase_37 AC 139 ms
15,468 KB
testcase_38 AC 153 ms
15,344 KB
testcase_39 AC 177 ms
15,336 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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