#1164115 (C++17) No.3539 Parentheses Square

• 問題: No.3539 Parentheses Square
• ユーザー: GOTKAKO
• 提出日時: 2026-05-09 15:49:18
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 87 ms / 2,000 ms
• コード長: 4,784 bytes
• コンパイル時間: 2,221 ms
• コンパイル使用メモリ: 246,216 KB
• 実行使用メモリ: 32,248 KB
• 最終ジャッジ日時: 2026-05-09 15:49:26
• 合計ジャッジ時間: 7,143 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 41

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct edge{ int to; long long cap; int rev;};
class Dinic{
    public:
    int n;
    vector<pair<int,int>> Es; //i番目の辺がどこにあるか.
    vector<vector<edge>> Graph;
 
    Dinic():n(0){}
    Dinic(int N):n(N),Graph(N){}
 
    int addedge(int u, int v, long long c){ //u->vに容量c.
        int m = Es.size();
        Es.push_back({u,Graph.at(u).size()});
        int gv = Graph.at(v).size(), gu = Graph.at(u).size();
        Graph.at(u).push_back(edge{v,c,gv});
        Graph.at(v).push_back(edge{u,0,gu});
        return m;
    }
 
    long long maxflow(int s, int t,long long limit = numeric_limits<long long>::max()){ //s->tにいくつ流せるか.
        long long ret = 0;
        vector<int> dist(n),search(n);
        auto bfs = [&]() -> void {
            queue<int> Q;
            fill(dist.begin(),dist.end(),-1);
            dist.at(s) = 0,Q.push(s);
            while(Q.size()){
                int pos = Q.front(); Q.pop();
                for(auto e : Graph.at(pos)){
                    if(e.cap == 0 || dist.at(e.to) != -1) continue;
                    dist.at(e.to) = dist.at(pos)+1;
                    if(e.to == t) return;
                    Q.push(e.to);
                }
            }
        };
        auto dfs = [&](auto dfs,int pos,long long f){
            if(pos == s) return f;
            long long flow = 0;
            int nowd = dist.at(pos);
            for(int &i=search.at(pos); i<Graph.at(pos).size(); i++){
                edge &e = Graph.at(pos).at(i);
                if(nowd <= dist.at(e.to) || Graph.at(e.to).at(e.rev).cap == 0) continue;
                long long now = dfs(dfs,e.to,min(f-flow,Graph.at(e.to).at(e.rev).cap));
                if(now <= 0) continue;
                Graph.at(pos).at(i).cap += now;
                Graph.at(e.to).at(e.rev).cap -= now;
                flow += now;
                if(flow == f) break;
            }
            return flow;
        };
 
        while(ret < limit){
            bfs();
            if(dist.at(t) == -1) break;
            fill(search.begin(),search.end(),0);
            while(ret < limit){
                long long f = dfs(dfs,t,limit-ret);
                if(f == 0) break;
                ret += f;
            }
        }
        return ret;
    }
 
    vector<pair<int,int>> mincost(int s){ //maxflowの後の復元
        vector<bool> already(n);
        queue<int> Q;
        Q.push(s),already.at(s) = true;
        while(Q.size()){
            int pos = Q.front(); Q.pop();
            for(auto e : Graph.at(pos)) if(e.cap && !already.at(e.to)) already.at(e.to) = true,Q.push(e.to);
        }
 
        vector<pair<int,int>> ret;
        for(auto [pos,i] : Es) if(already.at(pos)){
            edge &e = Graph.at(pos).at(i);
            if(!already.at(e.to)) ret.push_back({pos,e.to});
        }
        return ret; //[from,to]は辺の追加順になっている.
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    vector<string> S(N),T;
    vector<vector<int>> To(N);
    map<string,int> M;
    for(auto &s : S) cin >> s;

    auto solve = [&](int p) -> void {
        string s = S.at(p);
        vector<vector<bool>> dp(N+1,vector<bool>(N+1));
        dp.at(N).at(0) = true;
        for(int i=N-1; i>=0; i--){
            char c = s.at(i);
            if(c != ')') for(int k=0; k<N; k++) if(dp.at(i+1).at(k+1)) dp.at(i).at(k) = true;
            if(c != '(') for(int k=1; k<=N; k++) if(dp.at(i+1).at(k-1)) dp.at(i).at(k) = true;
        }
        
        string now(N,'-');
        int ok = 0;
        auto dfs = [&](auto dfs,int pos,int v) -> void {
            if(ok == N) return;
            if(v < 0 || dp.at(pos).at(v) == false) return;
            if(pos == N){
                if(!M.count(now)) M[now] = T.size(),T.emplace_back(now);
                To.at(p).push_back(M[now]),ok++;
                return;
            }
            if(s.at(pos) != ')'){
                now.at(pos) = '(';
                dfs(dfs,pos+1,v+1);
            }
            if(s.at(pos) != '('){
                now.at(pos) = ')';
                dfs(dfs,pos+1,v-1);
            }
        };
        dfs(dfs,0,0);
    };
    for(int i=0; i<N; i++) solve(i);

    int n = M.size()+N+2;
    int s = n-2,t = s+1;
    Dinic Z(n);
    for(int i=0; i<N; i++) Z.addedge(s,i,1);
    for(int i=0; i<M.size(); i++) Z.addedge(N+i,t,1);
    for(int i=0; i<N; i++) for(auto to : To.at(i)) Z.addedge(i,N+to,1);
    if(Z.maxflow(s,t) < N){cout << "-1\n"; return 0;}

    vector<string> answer(N);
    for(int i=0; i<N; i++) for(auto [to,cap,ign] : Z.Graph.at(i)) if(to != s && cap == 0){answer.at(i) = T.at(to-N); break;}
    for(auto &a : answer) cout << a << "\n";
}