結果

問題 No.1477 Lamps on Graph
ユーザー kichi2004_kichi2004_
提出日時 2021-04-16 20:08:53
言語 Rust
(1.77.0)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 2,708 bytes
コンパイル時間 1,205 ms
コンパイル使用メモリ 160,656 KB
実行使用メモリ 17,508 KB
最終ジャッジ日時 2023-09-15 20:21:29
合計ジャッジ時間 6,809 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 80 ms
8,588 KB
testcase_13 AC 85 ms
8,536 KB
testcase_14 AC 97 ms
9,332 KB
testcase_15 AC 37 ms
5,324 KB
testcase_16 AC 29 ms
6,296 KB
testcase_17 AC 33 ms
5,340 KB
testcase_18 AC 140 ms
11,996 KB
testcase_19 AC 83 ms
8,612 KB
testcase_20 AC 27 ms
4,376 KB
testcase_21 AC 123 ms
10,880 KB
testcase_22 AC 15 ms
4,376 KB
testcase_23 AC 49 ms
5,944 KB
testcase_24 AC 126 ms
10,572 KB
testcase_25 AC 37 ms
4,488 KB
testcase_26 AC 125 ms
12,184 KB
testcase_27 AC 42 ms
5,788 KB
testcase_28 AC 58 ms
8,224 KB
testcase_29 AC 58 ms
6,368 KB
testcase_30 AC 79 ms
6,672 KB
testcase_31 AC 47 ms
6,204 KB
testcase_32 AC 214 ms
17,000 KB
testcase_33 AC 170 ms
17,508 KB
testcase_34 AC 195 ms
17,240 KB
testcase_35 AC 173 ms
15,180 KB
testcase_36 AC 167 ms
15,312 KB
testcase_37 AC 134 ms
15,372 KB
testcase_38 AC 148 ms
15,436 KB
testcase_39 AC 166 ms
15,400 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused imports: `BTreeMap`, `BTreeSet`, `BinaryHeap`, `HashMap`
 --> 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`
 --> Main.rs:4:5
  |
4 | use std::convert::TryFrom;
  |     ^^^^^^^^^^^^^^^^^^^^^

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

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

warning: 4 warnings emitted

ソースコード

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