Submission #6198098
Source Code Expand
#![allow(unused_imports, unused_macros, dead_code)]
macro_rules! min {
(.. $x:expr) => {{
let mut it = $x.iter();
if let Some(z) = it.next() {
Some(it.fold(z, |x, y| min!(x, y)))
} else {
None
}
}};
($x:expr) => ($x);
($x:expr, $($ys:expr),*) => {{
let t = min!($($ys),*);
if $x < t { $x } else { t }
}}
}
macro_rules! max {
(.. $x:expr) => {{
let mut it = $x.iter();
if let Some(z) = it.next() {
Some(it.fold(z, |x, y| max!(x, y)))
} else {
None
}
}};
($x:expr) => ($x);
($x:expr, $($ys:expr),*) => {{
let t = max!($($ys),*);
if $x > t { $x } else { t }
}}
}
macro_rules! ewriteln {
($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
(.. $x:expr) => {{
let mut it = $x.iter();
if let Some(x) = it.next() { print!("{}", x); }
for x in it { print!(" {}", x); }
println!("");
}};
($x:expr) => { println!("{}", $x) };
($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}
const M: i64 = 1_000_000_007;
#[derive(Debug, Clone)]
enum UF { Root(usize), Child(usize) }
#[derive(Debug)]
struct UnionFind { table: Vec<UF> }
impl UnionFind {
fn new(n: usize) -> UnionFind {
UnionFind { table: vec![UF::Root(1); n], }
}
fn root(&mut self, x: usize) -> usize {
match self.table[x] {
UF::Root(_) => x,
UF::Child(parent) => {
let root = self.root(parent);
self.table[x] = UF::Child(root);
root
}
}
}
fn is_same(&mut self, x: usize, y: usize) -> bool {
self.root(x) == self.root(y)
}
fn size(&mut self, x: usize) -> usize {
let r = self.root(x);
match self.table[r] {
UF::Root(size) => size,
UF::Child(_) => 0
}
}
fn merge(&mut self, x: usize, y: usize) {
let root_x = self.root(x);
let root_y = self.root(y);
if root_x != root_y {
let size_x = self.size(root_x);
let size_y = self.size(root_y);
let (i, j) = if size_x > size_y {
(root_x, root_y)
} else {
(root_y, root_x)
};
self.table[i] = UF::Root(size_x + size_y);
self.table[j] = UF::Child(i);
}
}
}
fn main() {
let mut sc = Scanner::new();
let n: usize = sc.cin();
let m: usize = sc.cin();
let mut uf = UnionFind::new(n + m);
for i in 0..n {
let k: usize = sc.cin();
for _ in 0..k {
let l: usize = sc.cin();
uf.merge(i, l + n - 1);
}
}
let r = uf.root(0);
put!(if (0..n).all(|i| uf.root(i) == r) {
"YES"
} else {
"NO"
});
}
use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
fn cin<T: FromStr>(&mut self) -> T {
while self.buffer.len() == 0 {
let mut line = String::new();
let _ = self.stdin.read_line(&mut line);
for w in line.split_whitespace() {
self.buffer.push_back(String::from(w));
}
}
self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
}
}
Submission Info
Submission Time |
|
Task |
C - Interpretation |
User |
cympfh |
Language |
Rust (1.15.1) |
Score |
400 |
Code Size |
3835 Byte |
Status |
AC |
Exec Time |
27 ms |
Memory |
8444 KB |
Compile Error
warning: unknown lint: `unused_macros`, #[warn(unknown_lints)] on by default
--> ./Main.rs:1:26
|
1 | #![allow(unused_imports, unused_macros, dead_code)]
| ^^^^^^^^^^^^^
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
200 / 200 |
200 / 200 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
4352 KB |
01-02.txt |
AC |
2 ms |
4352 KB |
01-03.txt |
AC |
2 ms |
4352 KB |
01-04.txt |
AC |
2 ms |
4352 KB |
01-05.txt |
AC |
2 ms |
4352 KB |
01-06.txt |
AC |
2 ms |
4352 KB |
01-07.txt |
AC |
2 ms |
4352 KB |
01-08.txt |
AC |
2 ms |
4352 KB |
01-09.txt |
AC |
2 ms |
4352 KB |
01-10.txt |
AC |
2 ms |
4352 KB |
02-01.txt |
AC |
14 ms |
6396 KB |
02-02.txt |
AC |
23 ms |
4352 KB |
02-03.txt |
AC |
14 ms |
4352 KB |
02-04.txt |
AC |
23 ms |
8444 KB |
02-05.txt |
AC |
23 ms |
4352 KB |
02-06.txt |
AC |
23 ms |
8444 KB |
02-07.txt |
AC |
25 ms |
6396 KB |
02-08.txt |
AC |
22 ms |
6396 KB |
02-09.txt |
AC |
27 ms |
8444 KB |
02-10.txt |
AC |
21 ms |
8444 KB |
02-11.txt |
AC |
21 ms |
8444 KB |
02-12.txt |
AC |
21 ms |
6396 KB |
02-13.txt |
AC |
21 ms |
6396 KB |
sample-01.txt |
AC |
2 ms |
4352 KB |
sample-02.txt |
AC |
2 ms |
4352 KB |