Submission #2175866


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 mut sns = Sns::new(n, i.read_vec(g));
    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 99
Code Size 5466 Byte
Status TLE
Exec Time 2103 ms
Memory 4352 KB

Compile Error

warning: method is never used: `reset`, #[warn(dead_code)] on by default
  --> ./Main.rs:70:5
   |
70 |     fn reset(&mut self, n: usize, p: &[usize]) {
   |     ^

Judge Result

Set Name part All
Score / Max Score 99 / 99 0 / 1
Status
AC × 27
AC × 44
TLE × 17
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 AC 2 ms 4352 KB
sample_02.txt AC 2 ms 4352 KB
sample_03.txt AC 2 ms 4352 KB
sample_04.txt AC 2 ms 4352 KB
sample_05.txt AC 2 ms 4352 KB
test_01_AB.txt AC 2 ms 4352 KB
test_02_AB.txt AC 2 ms 4352 KB
test_03_AB.txt AC 2 ms 4352 KB
test_04_AB.txt AC 2 ms 4352 KB
test_05_AB.txt AC 2 ms 4352 KB
test_06_AB.txt AC 2 ms 4352 KB
test_07_AB.txt AC 2 ms 4352 KB
test_08_AB.txt AC 2 ms 4352 KB
test_09_AB.txt AC 2 ms 4352 KB
test_10_AB.txt AC 2 ms 4352 KB
test_11_AB.txt AC 2 ms 4352 KB
test_12_AB.txt AC 2 ms 4352 KB
test_13_AB.txt AC 2 ms 4352 KB
test_14_AB.txt AC 2 ms 4352 KB
test_15_AB.txt AC 2 ms 4352 KB
test_16_AB.txt AC 2 ms 4352 KB
test_17_AB.txt AC 2 ms 4352 KB
test_18_AB.txt AC 2 ms 4352 KB
test_19_AB.txt AC 2 ms 4352 KB
test_20_AB.txt AC 2 ms 4352 KB
test_21_AB.txt AC 2 ms 4352 KB
test_22_AB.txt AC 2 ms 4352 KB
test_23_AB.txt AC 2 ms 4352 KB
test_24_AB.txt AC 2 ms 4352 KB
test_25_AB.txt AC 2 ms 4352 KB
test_26_A.txt TLE 2103 ms 4352 KB
test_27_A.txt TLE 2103 ms 4352 KB
test_28_A.txt TLE 2103 ms 4352 KB
test_29_A.txt TLE 2103 ms 4352 KB
test_30_A.txt TLE 2103 ms 4352 KB
test_31_A.txt TLE 2103 ms 4352 KB
test_32_A.txt TLE 2103 ms 4352 KB
test_33_A.txt TLE 2103 ms 4352 KB
test_34_A.txt TLE 2103 ms 4352 KB
test_35_A.txt TLE 2103 ms 4352 KB
test_36_A.txt TLE 2103 ms 4352 KB
test_37_A.txt TLE 2103 ms 4352 KB
test_38_A.txt AC 209 ms 4352 KB
test_39_A.txt AC 330 ms 4352 KB
test_40_A.txt AC 2 ms 4352 KB
test_41_AB.txt AC 2 ms 4352 KB
test_42_A.txt TLE 2103 ms 4352 KB
test_43_A.txt AC 3 ms 4352 KB
test_44_A.txt TLE 2103 ms 4352 KB
test_45_A.txt AC 1536 ms 4352 KB
test_46_A.txt TLE 2103 ms 4352 KB
test_47_AB.txt AC 2 ms 4352 KB
test_48_A.txt AC 28 ms 4352 KB
test_49_A.txt TLE 2103 ms 4352 KB
test_50_A.txt TLE 2103 ms 4352 KB
test_51_A.txt AC 2 ms 4352 KB