結果
問題 | No.2316 Freight Train |
ユーザー | Moss_Local |
提出日時 | 2023-05-26 21:26:46 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 7,395 bytes |
コンパイル時間 | 20,601 ms |
コンパイル使用メモリ | 376,728 KB |
実行使用メモリ | 5,864 KB |
最終ジャッジ日時 | 2024-12-25 04:47:01 |
合計ジャッジ時間 | 29,717 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 343 ms
5,548 KB |
testcase_04 | AC | 190 ms
5,248 KB |
testcase_05 | AC | 132 ms
5,248 KB |
testcase_06 | AC | 45 ms
5,248 KB |
testcase_07 | AC | 314 ms
5,248 KB |
testcase_08 | AC | 177 ms
5,864 KB |
testcase_09 | AC | 267 ms
5,248 KB |
testcase_10 | AC | 290 ms
5,248 KB |
testcase_11 | AC | 239 ms
5,484 KB |
testcase_12 | AC | 305 ms
5,248 KB |
testcase_13 | AC | 378 ms
5,736 KB |
testcase_14 | AC | 362 ms
5,740 KB |
testcase_15 | AC | 355 ms
5,736 KB |
testcase_16 | AC | 352 ms
5,736 KB |
testcase_17 | AC | 349 ms
5,736 KB |
testcase_18 | AC | 340 ms
5,692 KB |
testcase_19 | AC | 349 ms
5,744 KB |
testcase_20 | AC | 359 ms
5,736 KB |
testcase_21 | AC | 349 ms
5,740 KB |
testcase_22 | AC | 360 ms
5,740 KB |
testcase_23 | AC | 320 ms
5,740 KB |
testcase_24 | AC | 342 ms
5,740 KB |
testcase_25 | AC | 328 ms
5,248 KB |
testcase_26 | AC | 316 ms
5,248 KB |
testcase_27 | AC | 292 ms
5,248 KB |
testcase_28 | AC | 1 ms
5,248 KB |
コンパイルメッセージ
warning: unnecessary parentheses around type --> src/main.rs:66:15 | 66 | fn readi() -> (i64) { | ^ ^ | = note: `#[warn(unused_parens)]` on by default help: remove these parentheses | 66 - fn readi() -> (i64) { 66 + fn readi() -> i64 { | warning: unused variable: `i` --> src/main.rs:269:9 | 269 | for i in 0..m { | ^ help: if this is intentional, prefix it with an underscore: `_i` | = note: `#[warn(unused_variables)]` on by default warning: variable does not need to be mutable --> src/main.rs:261:9 | 261 | let mut vec: Vec<i64> = read_vec(); | ----^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default
ソースコード
// -*- coding:utf-8-unix -*-// #![feature(map_first_last)]#![allow(dead_code)]#![allow(unused_imports)]#![allow(unused_macros)]// use core::num;use std::cmp::*;use std::fmt::*;use std::hash::*;use std::iter::FromIterator;use std::*;use std::{cmp, collections, fmt, io, iter, ops, str};const INF: i64 = 1223372036854775807;const UINF: usize = INF as usize;const LINF: i64 = 2147483647;const INF128: i128 = 1223372036854775807000000000000;const MOD1: i64 = 1000000007;const MOD2: i64 = 998244353;const MOD: i64 = MOD1;// const MOD: i64 = MOD2;const UMOD: usize = MOD as usize;const M_PI: f64 = 3.14159265358979323846;// const MOD: i64 = INF;use cmp::Ordering::*;use std::collections::*;use std::io::stdin;use std::io::stdout;use std::io::Write;macro_rules! p {($x:expr) => {println!("{}", $x);};}macro_rules! d {($x:expr) => {println!("{:?}", $x);};}macro_rules! yn {($val:expr) => {if $val {println!("Yes");} else {println!("No");}};}fn main() {solve();}// use str::Chars;#[allow(dead_code)]fn read<T: std::str::FromStr>() -> T {let mut s = String::new();std::io::stdin().read_line(&mut s).ok();s.trim().parse().ok().unwrap()}#[allow(dead_code)]fn readi() -> (i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();iter.next().unwrap().parse::<i64>().unwrap()}#[allow(dead_code)]fn read_vec<T: std::str::FromStr>() -> Vec<T> {read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()}#[allow(dead_code)]fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {(0..n).map(|_| read_vec()).collect()}#[allow(dead_code)]fn readii() -> (i64, i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),)}#[allow(dead_code)]fn readiii() -> (i64, i64, i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),)}#[allow(dead_code)]fn readuu() -> (usize, usize) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)}#[allow(dead_code)]fn readff() -> (f64, f64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<f64>().unwrap(),iter.next().unwrap().parse::<f64>().unwrap(),)}fn readcc() -> (char, char) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<char>().unwrap(),iter.next().unwrap().parse::<char>().unwrap(),)}fn readuuu() -> (usize, usize, usize) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)}#[allow(dead_code)]fn readiiii() -> (i64, i64, i64, i64) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),iter.next().unwrap().parse::<i64>().unwrap(),)}#[allow(dead_code)]fn readuuuu() -> (usize, usize, usize, usize) {let mut str = String::new();let _ = stdin().read_line(&mut str).unwrap();let mut iter = str.split_whitespace();(iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),iter.next().unwrap().parse::<usize>().unwrap(),)}pub struct UnionFind {n: usize,// root node: -1 * component size// otherwise: parentparent_or_size: Vec<i32>,}impl UnionFind {// 0 <= size <= 10^8 is constrained.pub fn new(size: usize) -> Self {Self {n: size,parent_or_size: vec![-1; size],}}pub fn merge(&mut self, a: usize, b: usize) -> usize {assert!(a < self.n);assert!(b < self.n);let (mut x, mut y) = (self.leader(a), self.leader(b));if x == y {return x;}if -self.parent_or_size[x] < -self.parent_or_size[y] {std::mem::swap(&mut x, &mut y);}self.parent_or_size[x] += self.parent_or_size[y];self.parent_or_size[y] = x as i32;x}pub fn same(&mut self, a: usize, b: usize) -> bool {assert!(a < self.n);assert!(b < self.n);self.leader(a) == self.leader(b)}pub fn leader(&mut self, a: usize) -> usize {assert!(a < self.n);if self.parent_or_size[a] < 0 {return a;}self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;self.parent_or_size[a] as usize}pub fn size(&mut self, a: usize) -> usize {assert!(a < self.n);let x = self.leader(a);-self.parent_or_size[x] as usize}pub fn groups(&mut self) -> Vec<Vec<usize>> {let mut leader_buf = vec![0; self.n];let mut group_size = vec![0; self.n];for i in 0..self.n {leader_buf[i] = self.leader(i);group_size[leader_buf[i]] += 1;}let mut result = vec![Vec::new(); self.n];for i in 0..self.n {result[i].reserve(group_size[i]);}for i in 0..self.n {result[leader_buf[i]].push(i);}result.into_iter().filter(|x| !x.is_empty()).collect::<Vec<Vec<usize>>>()}pub fn connected_component_num(&mut self) -> usize {let mut set = HashSet::new();for i in 0..self.n {set.insert(self.leader(i));}set.len()}pub fn leader_vec(&mut self) -> Vec<usize> {let mut leader_buf = vec![0; self.n];for i in 0..self.n {leader_buf[i] = self.leader(i);}leader_buf}}fn solve() {let (n, m) = readuu();let mut vec: Vec<i64> = read_vec();let mut uf = UnionFind::new(n);for i in 0..n {if vec[i] == -1 {continue;}uf.merge(vec[i] as usize - 1, i);}for i in 0..m {let (a, b) = readuu();if uf.same(a - 1, b - 1) {println!("Yes");} else {println!("No");}}return;}