結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー pockyny
提出日時 2025-06-02 02:17:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 81 ms / 4,000 ms
コード長 3,713 bytes
コンパイル時間 1,494 ms
コンパイル使用メモリ 90,072 KB
実行使用メモリ 15,208 KB
最終ジャッジ日時 2025-06-02 02:17:43
合計ジャッジ時間 4,340 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;
struct UF{
    vector<int> par,sz;
    // 連結成分の親
    vector<int> cp_par;
    vector<vector<int>> mergeTree;
    UF(int n, bool useMergeTree = false){
        sz.resize(n); par.resize(n); cp_par.resize(n);
        for(int i=0;i<n;i++) sz[i] = 1, par[i] = i,cp_par[i] = i;
        if(useMergeTree){
            sz.resize(2*n); par.resize(2*n);
            for(int i=n;i<2*n;i++) sz[i] = 1, par[i] = i;
            mergeTree.resize(2*n);
        }
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x] = find(par[x]); 
    }
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x,y);
        sz[y] += sz[x];
        par[x] = y;
        cp_par[y] = same(cp_par[y],y) ? cp_par[x] : cp_par[y];
    }
    bool same(int x,int y){return find(x)==find(y);}
    void merge(int child,int parent){
        //parentが親,merge過程を表す木などで使用
        child = find(child); parent = find(parent);
        if(child==parent) return;
        mergeTree[parent].push_back(child);
        sz[parent] += sz[child];
        par[child] = parent;
    }
};

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<pll,pll> pllll;
const int SZ = 200000;
// 問題ごとに必要なものを実装
ll val[SZ + 10],cnt[SZ + 10],ans[SZ + 10];
struct Cmp{
    bool operator()(const pllll &l,const pllll &r){
        // cout << l.first.first << "/" << l.first.second << "," << r.first.first << "/" << r.first.second << endl;
        return l.first.first * r.first.second < l.first.second * r.first.first;
    }
};

// idとidの親をmergeして、新しい代表の値を返す
// 問題ごとに実装する
int merge(int id,UF &uf){
    id = uf.find(id);
    int pa = uf.find(uf.cp_par[id]);
    ll nv = val[pa] + val[id],nc = cnt[pa] + cnt[id];
    ll nans = ans[pa] + ans[id] + cnt[pa]*val[id];
    uf.unite(id,pa);
    int n_id = uf.find(id);
    val[n_id] = nv; cnt[n_id] = nc; ans[n_id] = nans;
    return n_id;
}

// 01OnTreeを解く
// input: p,a. pは根を0として、0-nの親の配列 (p[0] = -1;)
// output 根から順にtopological順序で、0-nを割りふってΣi*a[i]の最小化
ll TreeTopoMin(vector<ll> &p, vector<ll> &a){
    int i,n = p.size();
    UF uf(n);
    for(i=1;i<n;i++) uf.cp_par[i] = p[i];
    for(i=1;i<n;i++) val[i] = a[i],cnt[i] = 1;
    val[0] = 0; cnt[0] = 1;
    priority_queue<pllll,vector<pllll>,Cmp> que;
    int t = 0;
    // queに入れたものの有効無効の判定に使う
    vector<ll> tm_stamp(n);
    auto custom_push = [&](int id){
        que.push({{val[id],cnt[id]},{uf.find(id),t}});
        tm_stamp[uf.find(id)] = t;
        t++;
    };
    for(i=1;i<n;i++) custom_push(i);
    while(que.size()){
        auto [x,y] = que.top();
        que.pop();
        auto [v,c] = x;
        auto [id,stamp] = y;
        // queの中で有効 = 代表元かつ、stampが最新
        // 他の物によって更新されると、代表が変わるか、stampの更新が起きる
        if(uf.find(id)!=id || tm_stamp[id]!=stamp) continue;
        int n_id = merge(id,uf);
        if(!uf.same(0,n_id)) custom_push(n_id);
    }
    return ans[uf.find(0)];
}

int main(){
    int i,n; cin >> n;
    string s; cin >> s;
    vector<ll> p(n + 1),a(n + 1);
    for(i=1;i<=n;i++) cin >> a[i];
    int now = 0,mx = 0;
    p[0] = -1;
    for(char c:s){
        if(c=='('){
            mx++;
            p[mx] = now;
            now = mx;
        }else{
            now = p[now];
        }
    }
    cout << TreeTopoMin(p,a) << "\n";
}
0