結果

問題 No.3148 Min-Cost Destruction of Parentheses
ユーザー 👑 Nachia
提出日時 2025-05-16 21:27:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 59 ms / 4,000 ms
コード長 3,640 bytes
コンパイル時間 1,055 ms
コンパイル使用メモリ 91,668 KB
実行使用メモリ 12,584 KB
最終ジャッジ日時 2025-05-16 21:27:10
合計ジャッジ時間 3,106 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(i64 i=0; i<i64(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;

#include <queue>

namespace nachia {

struct Dsu{
private:
    int N;
    std::vector<int> P;
    std::vector<int> H;
public:
    Dsu() : N(0) {}
    Dsu(int n) : N(n), P(n, -1), H(n) {
        for(int i=0; i<n; i++) H[i] = i;
    }
    int leader(int u){
        if(P[u] < 0) return u;
        int v = P[u];
        while(P[v] >= 0){ P[u] = P[v]; u = v; v = P[v]; }
        return P[u];
    }
    int append(int label){
        int n = P.size();
        P.push_back(-1);
        H.push_back(label);
        return n;
    }
    int append(){ return append(int(P.size())); }
    int label(int u){ return H[leader(u)]; }
    int operator[](int u){ return H[leader(u)]; }
    void merge(int u, int v, int newLabel){
        u = leader(u);
        v = leader(v);
        if(u == v){ H[u] = newLabel; return; }
        N--;
        if(-P[u] < -P[v]) std::swap(u, v);
        P[u] += P[v];
        H[P[v] = u] = newLabel;
    }
    int merge(int u, int v){ merge(u, v, u); return u; }
    int count(){ return N; }
    int size(int u){ return -P[leader(u)]; }
    bool same(int u, int v){ return leader(u) == leader(v); }
};

} // namespace nachia

namespace nachia {

template<class Weight>
std::vector<int> TreeSearchMinimumInversionWithParentArray(
    std::vector<int> par,
    std::vector<Weight> D,
    std::vector<Weight> C,
    int start
){
    struct Frac {
        Weight d;
        Weight c;
        int root;
        int label;
        bool operator<(const Frac& r) const {
            // (0,0) smallest
            if(r.c == 0 && r.d == 0) return false;
            if(c == 0 && d == 0) return true;

            // c / d increasing
            return c * r.d < d * r.c;
        }
    };
    int n = int(par.size());
    std::priority_queue<Frac> que;
    nachia::Dsu dsu(n);
    for(int v=0; v<n; v++) if(par[v] != -1){
        que.push({ D[v], C[v], v, 0 });
    }
    std::vector<int> linkA(n);
    for(int i=0; i<n; i++) linkA[i] = i;
    std::vector<int> label(n, 0);
    while(que.size()){
        auto q = que.top(); que.pop();
        int v = q.root;
        if(label[v] != q.label) continue;
        int w = dsu[par[v]];
        D[w] = D[w] + D[v];
        C[w] = C[w] + C[v];
        dsu.merge(v, w, w);
        if(par[w] != -1){
            que.push({ D[w], C[w], w, ++label[w] });
        }
        std::swap(linkA[v], linkA[w]);
    }
    std::vector<int> ans;
    ans.push_back(linkA[start]);
    while(ans.back() != start) ans.push_back(linkA[ans.back()]);
    std::reverse(ans.begin(), ans.end());
    return ans;
}

}

void testcase(){
    i64 N; cin >> N;
    string S; cin >> S; S = "(" + S + ")";
    vector<i64> A(N+1); rep(i,N) cin >> A[i+1];
    N++;
    i64 p = 0, sp = 0;
    vector<int> par(N, -1);
    auto dfs = [&](auto& dfs) -> i64 {
        i64 i = p++; sp++;
        while(S[sp] != ')'){
            par[dfs(dfs)] = i;
        }
        sp++;
        return i;
    };
    dfs(dfs);
    vector<i64> D(N,1);
    auto ans = nachia::TreeSearchMinimumInversionWithParentArray(par, D, A, 0);
    i64 val = 0;
    rep(i,N) val += i * A[ans[i]];
    cout << val << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}
0