結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー pockyny
提出日時 2025-06-02 01:50:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 69 ms / 4,000 ms
コード長 3,247 bytes
コンパイル時間 1,246 ms
コンパイル使用メモリ 85,840 KB
実行使用メモリ 10,876 KB
最終ジャッジ日時 2025-06-02 01:50:46
合計ジャッジ時間 3,675 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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,ll> plll;
ll p[200010],a[200010];
ll val[200010],cnt[200010],ans[200010];
struct Cmp{
    bool operator()(const plll &l,const plll &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;
    }
};


int main(){
    int i,n; cin >> n;
    string s; cin >> s;
    for(i=1;i<=n;i++) cin >> a[i];
    int now = 0,mx = 0;
    for(char c:s){
        if(c=='('){
            mx++;
            p[mx] = now;
            now = mx;
        }else{
            now = p[now];
        }
    }
    UF uf(n + 1);
    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;
    priority_queue<plll,vector<plll>,Cmp> que;
    for(i=1;i<=n;i++) que.push({{val[i],cnt[i]},uf.find(i)});
    val[0] = 0; cnt[0] = 1;
    while(que.size()){
        auto [x,id] = que.top();
        que.pop();
        auto [v,c] = x;
        if(uf.find(id)!=id || val[id]!=v || cnt[id]!=c) continue;
        int pa = uf.find(uf.cp_par[id]);
        // cout << "id == " << id << " pa == " << pa << " " << v << " " << c << "\n";
        // cout << "q_s " << que.size() << "\n";
        ll nv = val[pa] + v,nc = cnt[pa] + c;
        ll nans = ans[pa] + ans[id] + cnt[pa]*v;
        uf.unite(id,pa);
        int n_id = uf.find(id);
        val[n_id] = nv; cnt[n_id] = nc; ans[n_id] = nans;
        if(!uf.same(0,n_id)) que.push({{val[n_id],cnt[n_id]},n_id});
        // for(i=0;i<=n;i++) cout << "{" << val[i] << "," << cnt[i] << "," << ans[i] << "} ";
        // cout << "\n";
    }
    cout << ans[uf.find(0)] << "\n";

    // priority_queue<plll,vector<plll>,Cmp> que;
    // que.push({{1,2},2});
    // que.push({{1,1},1});
    // while(que.size()){
    //     auto [_,id] = que.top();
    //     que.pop();
    //     cout << "id == " << id << "\n";
    // }
}
0