Submission #2175862
Source Code Expand
use std::str::FromStr;
use std::io::*;
use std::cmp::*;
pub fn main() {
let i = stdin();
let mut o = Vec::new();
run(&mut i.lock(), &mut o);
stdout().write_all(&o).unwrap();
}
fn run<R: BufRead, W: Write>(i: &mut R, o: &mut W) {
let mut i = AtRead::from(i);
let (n, g, e) = i.read3::<usize, usize, usize>();
let p: Vec<usize> = i.read_vec(g);
return;
let mut sns = Sns::new(n, p);
for _ in 0..e {
sns.push_link(i.read2());
}
writeln!(o, "{}", solve(&mut sns)).unwrap();
}
fn solve(sns: &mut Sns) -> usize {
sns.update_visits();
sns.update_links();
let mut m = 1;
while m < sns.result {
fn comb(sns: &mut Sns, m: usize, next: usize) {
if sns.cuts.len() == m {
sns.update_result();
} else {
for i in next..sns.links.len() {
let link = sns.links[i];
sns.begin_cut_link(link);
comb(sns, m, i + 1);
sns.end_cut_link(link);
if sns.result <= m {
return;
}
}
}
}
comb(sns, m, 0);
m += 1;
}
sns.result
}
#[derive(Debug, Clone)]
struct Sns {
n: usize, // ユーザー数
f: Vec<Vec<bool>>, // f[a][b] がtrueだとaとbはフレンド
v: Vec<bool>, // ID nのユーザーが間接的フレンドだとv[n]はtrue
p: Vec<usize>, // ターゲットのリスト
q: Vec<usize>, // self.v 計算用バッファ
links: Vec<(usize, usize)>,
cuts: Vec<(usize, usize)>,
result: usize,
}
impl Sns {
fn new(n: usize, p: Vec<usize>) -> Self {
Sns {
n: n,
f: vec![vec![false; n]; n],
q: Vec::new(),
p: p,
v: vec![false; n],
links: Vec::new(),
cuts: Vec::new(),
result: usize::max_value(),
}
}
fn reset(&mut self, n: usize, p: &[usize]) {
self.n = n;
self.f.resize(n, Vec::new());
for i in 0..n {
self.f[i].clear();
self.f[i].resize(n, false);
}
self.q.clear();
self.p.clear();
self.p.extend(p);
self.v.clear();
self.v.resize(n, false);
self.links.clear();
self.cuts.clear();
self.result = usize::max_value();
}
fn push_link(&mut self, ab: (usize, usize)) {
self.links.push(ab);
self.set_friend(ab, true);
}
fn set_friend(&mut self, (a, b): (usize, usize), value: bool) {
self.f[a][b] = value;
self.f[b][a] = value;
}
fn update_visits(&mut self) {
let n = self.n;
let v = &mut self.v;
let q = &mut self.q;
v.clear();
v.resize(n, false);
q.clear();
q.push(0);
v[0] = true;
while let Some(i0) = q.pop() {
let f = &self.f[i0];
for i1 in 1..n {
if f[i1] && !v[i1] {
v[i1] = true;
q.push(i1);
}
}
}
}
fn update_links(&mut self) {
self.links = self.links.iter().cloned().filter(|i| self.v[i.0]).collect();
self.p = self.p.iter().cloned().filter(|&i| self.v[i]).collect();
self.result = self.p.len();
}
fn update_result(&mut self) {
self.update_visits();
let r = self.p.iter().filter(|&&i| self.v[i]).count() + self.cuts.len();
self.result = min(self.result, r);
// println!("");
// println!("result : {}", r);
// print!("cut : ");
// for &c in self.cuts.iter() {
// print!("{:?},", c);
// }
// println!("");
// print!("p : ");
// for &p in self.p.iter().filter(|&&i| self.v[i]) {
// print!("{:?},", p);
// }
// println!("");
}
fn begin_cut_link(&mut self, ab: (usize, usize)) {
self.set_friend(ab, false);
self.cuts.push(ab);
}
fn end_cut_link(&mut self, ab: (usize, usize)) {
self.set_friend(ab, true);
self.cuts.pop();
}
}
struct AtRead<'a, R: BufRead + 'a> {
r: &'a mut R,
s: String,
}
macro_rules! fn_read {
{$f:ident($($v:ident: $t:ident),*)} => {
fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
let i = &mut self.next().split(' ');
$(
let $v = next(i);
)*
($($v),*)
}
};
}
impl<'a, R: BufRead + 'a> AtRead<'a, R> {
fn from(r: &'a mut R) -> Self {
AtRead {
r: r,
s: String::new(),
}
}
fn next(&mut self) -> &str {
self.s.clear();
self.r.read_line(&mut self.s).unwrap();
self.s.trim()
}
fn_read! { read2(v1: T1, v2: T2) }
fn_read! { read3(v1: T1, v2: T2, v3: T3) }
fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
self.next()
.split(' ')
.take(n)
.map(|x| x.parse().ok().unwrap())
.collect()
}
}
fn next<'a, T: FromStr, I: std::iter::Iterator<Item = &'a str>>(i: &mut I) -> T {
i.next().unwrap().parse().ok().unwrap()
}
Submission Info
Submission Time |
|
Task |
D - 浮気予防 |
User |
frozenlib |
Language |
Rust (1.15.1) |
Score |
0 |
Code Size |
5507 Byte |
Status |
WA |
Exec Time |
2 ms |
Memory |
4352 KB |
Compile Error
warning: unused variable: `o`, #[warn(unused_variables)] on by default
--> ./Main.rs:12:41
|
12 | fn run<R: BufRead, W: Write>(i: &mut R, o: &mut W) {
| ^
warning: unused variable: `n`, #[warn(unused_variables)] on by default
--> ./Main.rs:14:10
|
14 | let (n, g, e) = i.read3::<usize, usize, usize>();
| ^
warning: unused variable: `e`, #[warn(unused_variables)] on by default
--> ./Main.rs:14:16
|
14 | let (n, g, e) = i.read3::<usize, usize, usize>();
| ^
warning: unused variable: `p`, #[warn(unused_variables)] on by default
--> ./Main.rs:15:9
|
15 | let p: Vec<usize> = i.read_vec(g);
| ^
warning: unreachable statement, #[warn(unreachable_code)] on by default
--> ./Main.rs:17:5
|
17 | let mut sns = Sns::new(n, p);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
warning: method is never used: `reset`, #[warn(dead_code)] on by default
--> ./Main.rs:72:5
|
72 | fn reset(&mut self,...
Judge Result
Set Name |
part |
All |
Score / Max Score |
0 / 99 |
0 / 1 |
Status |
|
|
Set Name |
Test Cases |
part |
test_01_AB.txt, test_02_AB.txt, test_03_AB.txt, test_04_AB.txt, test_05_AB.txt, test_06_AB.txt, test_07_AB.txt, test_08_AB.txt, test_09_AB.txt, test_10_AB.txt, test_11_AB.txt, test_12_AB.txt, test_13_AB.txt, test_14_AB.txt, test_15_AB.txt, test_16_AB.txt, test_17_AB.txt, test_18_AB.txt, test_19_AB.txt, test_20_AB.txt, test_21_AB.txt, test_22_AB.txt, test_23_AB.txt, test_24_AB.txt, test_25_AB.txt, test_41_AB.txt, test_47_AB.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, test_01_AB.txt, test_02_AB.txt, test_03_AB.txt, test_04_AB.txt, test_05_AB.txt, test_06_AB.txt, test_07_AB.txt, test_08_AB.txt, test_09_AB.txt, test_10_AB.txt, test_11_AB.txt, test_12_AB.txt, test_13_AB.txt, test_14_AB.txt, test_15_AB.txt, test_16_AB.txt, test_17_AB.txt, test_18_AB.txt, test_19_AB.txt, test_20_AB.txt, test_21_AB.txt, test_22_AB.txt, test_23_AB.txt, test_24_AB.txt, test_25_AB.txt, test_26_A.txt, test_27_A.txt, test_28_A.txt, test_29_A.txt, test_30_A.txt, test_31_A.txt, test_32_A.txt, test_33_A.txt, test_34_A.txt, test_35_A.txt, test_36_A.txt, test_37_A.txt, test_38_A.txt, test_39_A.txt, test_40_A.txt, test_41_AB.txt, test_42_A.txt, test_43_A.txt, test_44_A.txt, test_45_A.txt, test_46_A.txt, test_47_AB.txt, test_48_A.txt, test_49_A.txt, test_50_A.txt, test_51_A.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
WA |
2 ms |
4352 KB |
sample_02.txt |
WA |
2 ms |
4352 KB |
sample_03.txt |
WA |
2 ms |
4352 KB |
sample_04.txt |
WA |
2 ms |
4352 KB |
sample_05.txt |
WA |
2 ms |
4352 KB |
test_01_AB.txt |
WA |
2 ms |
4352 KB |
test_02_AB.txt |
WA |
2 ms |
4352 KB |
test_03_AB.txt |
WA |
2 ms |
4352 KB |
test_04_AB.txt |
WA |
2 ms |
4352 KB |
test_05_AB.txt |
WA |
2 ms |
4352 KB |
test_06_AB.txt |
WA |
2 ms |
4352 KB |
test_07_AB.txt |
WA |
2 ms |
4352 KB |
test_08_AB.txt |
WA |
2 ms |
4352 KB |
test_09_AB.txt |
WA |
2 ms |
4352 KB |
test_10_AB.txt |
WA |
2 ms |
4352 KB |
test_11_AB.txt |
WA |
2 ms |
4352 KB |
test_12_AB.txt |
WA |
2 ms |
4352 KB |
test_13_AB.txt |
WA |
2 ms |
4352 KB |
test_14_AB.txt |
WA |
2 ms |
4352 KB |
test_15_AB.txt |
WA |
2 ms |
4352 KB |
test_16_AB.txt |
WA |
2 ms |
4352 KB |
test_17_AB.txt |
WA |
2 ms |
4352 KB |
test_18_AB.txt |
WA |
2 ms |
4352 KB |
test_19_AB.txt |
WA |
2 ms |
4352 KB |
test_20_AB.txt |
WA |
2 ms |
4352 KB |
test_21_AB.txt |
WA |
2 ms |
4352 KB |
test_22_AB.txt |
WA |
2 ms |
4352 KB |
test_23_AB.txt |
WA |
2 ms |
4352 KB |
test_24_AB.txt |
WA |
2 ms |
4352 KB |
test_25_AB.txt |
WA |
2 ms |
4352 KB |
test_26_A.txt |
WA |
2 ms |
4352 KB |
test_27_A.txt |
WA |
2 ms |
4352 KB |
test_28_A.txt |
WA |
2 ms |
4352 KB |
test_29_A.txt |
WA |
2 ms |
4352 KB |
test_30_A.txt |
WA |
2 ms |
4352 KB |
test_31_A.txt |
WA |
2 ms |
4352 KB |
test_32_A.txt |
WA |
2 ms |
4352 KB |
test_33_A.txt |
WA |
2 ms |
4352 KB |
test_34_A.txt |
WA |
2 ms |
4352 KB |
test_35_A.txt |
WA |
2 ms |
4352 KB |
test_36_A.txt |
WA |
2 ms |
4352 KB |
test_37_A.txt |
WA |
2 ms |
4352 KB |
test_38_A.txt |
WA |
2 ms |
4352 KB |
test_39_A.txt |
WA |
2 ms |
4352 KB |
test_40_A.txt |
WA |
2 ms |
4352 KB |
test_41_AB.txt |
WA |
2 ms |
4352 KB |
test_42_A.txt |
WA |
2 ms |
4352 KB |
test_43_A.txt |
WA |
2 ms |
4352 KB |
test_44_A.txt |
WA |
2 ms |
4352 KB |
test_45_A.txt |
WA |
2 ms |
4352 KB |
test_46_A.txt |
WA |
2 ms |
4352 KB |
test_47_AB.txt |
WA |
2 ms |
4352 KB |
test_48_A.txt |
WA |
2 ms |
4352 KB |
test_49_A.txt |
WA |
2 ms |
4352 KB |
test_50_A.txt |
WA |
2 ms |
4352 KB |
test_51_A.txt |
WA |
2 ms |
4352 KB |