結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー koba-e964
提出日時 2025-05-17 14:57:59
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 128 ms / 4,000 ms
コード長 5,448 bytes
コンパイル時間 18,851 ms
コンパイル使用メモリ 399,436 KB
実行使用メモリ 17,408 KB
最終ジャッジ日時 2025-05-17 14:58:28
合計ジャッジ時間 22,066 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($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)*}
    };
}

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)*}
    };
}

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:tt ]) => {{
        let len = read_value!($next, usize);
        read_value!($next, [$t; len])
    }};
    ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));
}

#[allow(unused)]
trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); }
impl<T: PartialOrd> Change for T {
    fn chmax(&mut self, x: T) { if *self < x { *self = x; } }
    fn chmin(&mut self, x: T) { if *self > x { *self = x; } }
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}

#[derive(Eq, Clone, Copy, Debug)]
struct AB {
    a: i64,
    b: i64,
}
impl std::cmp::PartialEq for AB {
    fn eq(&self, &Self { a: oa, b: ob }: &Self) -> bool {
        self.a * ob == oa * self.b
    }
}
impl std::cmp::PartialOrd for AB {
    fn partial_cmp(&self, &Self { a: oa, b: ob }: &Self) -> Option<std::cmp::Ordering> {
        (self.a * ob).partial_cmp(&(oa * self.b))
    }
}
impl std::cmp::Ord for AB {
    fn cmp(&self, &Self { a: oa, b: ob }: &Self) -> std::cmp::Ordering {
        (self.a * ob).cmp(&(oa * self.b))
    }
}

fn dfs1(s: &[char], bank: &mut usize, p: &mut [usize]) -> (usize, usize) {
    assert_eq!(s[0], '(');
    let me = *bank;
    *bank += 1;
    let mut cur = 1;
    while cur < s.len() && s[cur] == '(' {
        let (ch, pos) = dfs1(&s[cur..], bank, p);
        p[ch] = me;
        cur += pos;
    }
    assert_eq!(s[cur], ')');
    (me, cur + 1)
}

const DEBUG: bool = false;

fn solve() {
    input! {
        n: usize,
        s: chars,
        a: [i64; n],
    }
    let mut s = s;
    s.insert(0, '(');
    s.push(')');
    let mut p = vec![0; n + 1];
    p[0] = n + 1;
    dfs1(&s, &mut 0, &mut p);
    let mut ch = vec![BTreeSet::new(); n + 1];
    for i in 1..=n {
        ch[p[i]].insert(i);
    }

    let mut que = BinaryHeap::new();
    let mut abs = vec![AB { a: 0, b: 1 }; n + 1];
    for i in 1..=n {
        abs[i] = AB { a: a[i - 1], b: 1 };
        que.push((abs[i], i));
    }
    let mut valid = vec![true; n + 1];
    let mut cost = 0;
    let mut nvert = n + 1;
    let mut root = 0;
    while let Some((alleged, idx)) = que.pop() {
        if abs[idx].a != alleged.a || abs[idx].b != alleged.b {
            continue;
        }
        // eprintln!("taken: {:?} => {:?}", idx, abs[idx]);
        if !valid[idx] {
            continue;
        }
        let par = p[idx];

        let merged = AB {
            a: abs[par].a + abs[idx].a,
            b: abs[par].b + abs[idx].b,
        };
        cost += abs[par].b * abs[idx].a;

        let newidx = if ch[par].len() <= ch[idx].len() { idx } else { par };
        if newidx == par {
            // up
            let tmp = std::mem::take(&mut ch[idx]);
            for v in tmp {
                ch[par].insert(v);
                p[v] = par;
            }
            ch[par].remove(&idx);
            valid[idx] = false;
            p[idx] = n + 1;
        } else {
            // down
            let tmp = std::mem::take(&mut ch[par]);
            for v in tmp {
                if v == idx {
                    continue;
                }
                ch[idx].insert(v);
                p[v] = idx;
            }
            let parpar = p[par];
            if parpar != n + 1 {
                ch[parpar].insert(idx);
                ch[parpar].remove(&par);
            }
            valid[par] = false;
            p[par] = n + 1;
            p[idx] = parpar;
        }
        abs[newidx] = merged;
        abs[idx + par - newidx] = AB { a: 0, b: 0 };
        if par == root {
            root = newidx;
        }
        if newidx != root {
            que.push((merged, newidx));
        }
        assert!(ch[idx + par - newidx].is_empty());
        if DEBUG {
            eprintln!("{:?}", ch);
            eprintln!("{:?}", p);
            eprintln!("{:?}", abs);
            eprintln!("cost: {:?}", cost);
            eprintln!("que: {:?}", que);
        }
        nvert -= 1;
        if nvert == 1 {
            break;
        }
    }
    println!("{cost}");
}
0