結果
| 問題 | No.849 yuki国の分割統治 |
| ユーザー |
 masaki.arizuka
|
| 提出日時 | 2019-09-23 00:32:06 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,431 bytes |
| コンパイル時間 | 2,674 ms |
| コンパイル使用メモリ | 203,624 KB |
| 実行使用メモリ | 40,624 KB |
| 最終ジャッジ日時 | 2023-10-19 07:29:29 |
| 合計ジャッジ時間 | 10,038 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,348 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 221 ms
34,044 KB |
| testcase_17 | WA | - |
| testcase_18 | AC | 233 ms
34,984 KB |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | AC | 129 ms
14,164 KB |
| testcase_25 | AC | 257 ms
37,784 KB |
| testcase_26 | AC | 1 ms
4,348 KB |
| testcase_27 | AC | 1 ms
4,348 KB |
| testcase_28 | AC | 1 ms
4,348 KB |
| testcase_29 | WA | - |
コンパイルメッセージ
warning: unused variable: `k`
--> Main.rs:146:10
|
146 | for (k, v) in mod_a {
| ^ help: if this is intentional, prefix it with an underscore: `_k`
|
= note: `#[warn(unused_variables)]` on by default
warning: unused variable: `k`
--> Main.rs:151:10
|
151 | for (k, v) in mod_c {
| ^ help: if this is intentional, prefix it with an underscore: `_k`
warning: unused variable: `k`
--> Main.rs:157:10
|
157 | for (k, v) in mod_b {
| ^ help: if this is intentional, prefix it with an underscore: `_k`
warning: unused variable: `k`
--> Main.rs:162:10
|
162 | for (k, v) in mod_d {
| ^ help: if this is intentional, prefix it with an underscore: `_k`
warning: 4 warnings emitted
ソースコード
#[allow(unused_macros)]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
let mut $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
#[allow(unused_macros)]
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
#[allow(unused_macros)]
macro_rules! debug {
($($a:expr),*) => {
#[cfg(debug_assertions)]
writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
}
}
#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};
#[derive(Debug)]
pub struct UnionFind {
par: Vec<usize>,
}
impl UnionFind {
pub fn new(n: usize) -> UnionFind {
let mut vec = vec![0; n];
for i in 0..n {
vec[i] = i;
}
UnionFind { par: vec }
}
pub fn find(&mut self, x: usize) -> usize {
if x == self.par[x] {
x
} else {
let par = self.par[x];
let res = self.find(par);
self.par[x] = res;
res
}
}
pub fn same(&mut self, a: usize, b: usize) -> bool {
self.find(a) == self.find(b)
}
pub fn unite(&mut self, a: usize, b: usize) {
let apar = self.find(a);
let bpar = self.find(b);
self.par[apar] = bpar;
}
}
fn main() {
let out = std::io::stdout();
let mut out = BufWriter::new(out.lock());
macro_rules! puts {
($($format:tt)*) => (write!(out,$($format)*).unwrap());
}
input!{
mut a: usize,
mut b: usize,
mut c: usize,
mut d: usize,
n: usize,
xys: [(usize, usize); n]
}
if a == 0 { a = 1e10 as usize; }
if b == 0 { b = 1e10 as usize; }
if c == 0 { c = 1e10 as usize; }
if d == 0 { d = 1e10 as usize; }
use std::collections::HashMap;
let mut mod_a = HashMap::new();
let mut mod_b = HashMap::new();
let mut mod_c = HashMap::new();
let mut mod_d = HashMap::new();
for i in 0..n {
let (x, y) = xys[i];
debug!(x, x%a, x%c, y, y%b, y%d);
mod_a.entry(x%a).or_insert(vec![]).push(i);
mod_c.entry(x%c).or_insert(vec![]).push(i);
mod_b.entry(y%b).or_insert(vec![]).push(i);
mod_d.entry(y%d).or_insert(vec![]).push(i);
}
let mut ufx = UnionFind::new(n);
let mut ufy = UnionFind::new(n);
for (k, v) in mod_a {
debug!(k, v);
let v0 = v[0];
for idx in v { ufx.unite(v0, idx); }
}
for (k, v) in mod_c {
debug!(k, v);
let v0 = v[0];
for idx in v { ufx.unite(v0, idx); }
}
for (k, v) in mod_b {
debug!(k, v);
let v0 = v[0];
for idx in v { ufy.unite(v0, idx); }
}
for (k, v) in mod_d {
debug!(k, v);
let v0 = v[0];
for idx in v { ufy.unite(v0, idx); }
}
let mut pairs = vec![];
for i in 0..n {
pairs.push((ufx.find(i), ufy.find(i)));
}
debug!(pairs);
pairs.sort();
pairs.dedup();
debug!(pairs);
puts!("{}\n", pairs.len());
}