#724764 (C++17) No.1789 Tree Growing

提出ソース

結果

問題	No.1789 Tree Growing
ユーザー	👑 Nachia
提出日時	2021-12-18 00:52:30
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3,310 ms / 5,000 ms
コード長	5,371 bytes
コンパイル時間	1,525 ms
コンパイル使用メモリ	102,476 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-15 01:59:55
合計ジャッジ時間	17,169 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	3 ms 6,948 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	3 ms 6,944 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	4 ms 6,940 KB
testcase_22	AC	4 ms 6,944 KB
testcase_23	AC	4 ms 6,944 KB
testcase_24	AC	4 ms 6,940 KB
testcase_25	AC	7 ms 6,940 KB
testcase_26	AC	7 ms 6,944 KB
testcase_27	AC	6 ms 6,944 KB
testcase_28	AC	6 ms 6,944 KB
testcase_29	AC	7 ms 6,940 KB
testcase_30	AC	8 ms 6,944 KB
testcase_31	AC	8 ms 6,944 KB
testcase_32	AC	8 ms 6,940 KB
testcase_33	AC	8 ms 6,940 KB
testcase_34	AC	9 ms 6,944 KB
testcase_35	AC	7 ms 6,940 KB
testcase_36	AC	10 ms 6,944 KB
testcase_37	AC	10 ms 6,944 KB
testcase_38	AC	9 ms 6,940 KB
testcase_39	AC	6 ms 6,940 KB
testcase_40	AC	8 ms 6,940 KB
testcase_41	AC	11 ms 6,940 KB
testcase_42	AC	10 ms 6,944 KB
testcase_43	AC	12 ms 6,944 KB
testcase_44	AC	11 ms 6,944 KB
testcase_45	AC	10 ms 6,944 KB
testcase_46	AC	12 ms 6,940 KB
testcase_47	AC	13 ms 6,944 KB
testcase_48	AC	13 ms 6,940 KB
testcase_49	AC	12 ms 6,944 KB
testcase_50	AC	12 ms 6,940 KB
testcase_51	AC	11 ms 6,940 KB
testcase_52	AC	13 ms 6,944 KB
testcase_53	AC	13 ms 6,940 KB
testcase_54	AC	8 ms 6,940 KB
testcase_55	AC	7 ms 6,940 KB
testcase_56	AC	34 ms 6,940 KB
testcase_57	AC	123 ms 6,940 KB
testcase_58	AC	12 ms 6,940 KB
testcase_59	AC	47 ms 6,940 KB
testcase_60	AC	972 ms 6,944 KB
testcase_61	AC	578 ms 6,940 KB
testcase_62	AC	1,526 ms 6,940 KB
testcase_63	AC	1,838 ms 6,940 KB
testcase_64	AC	366 ms 6,940 KB
testcase_65	AC	757 ms 6,944 KB
testcase_66	AC	133 ms 6,944 KB
testcase_67	AC	218 ms 6,944 KB
testcase_68	AC	249 ms 6,940 KB
testcase_69	AC	153 ms 6,944 KB
testcase_70	AC	627 ms 6,944 KB
testcase_71	AC	466 ms 6,944 KB
testcase_72	AC	3,310 ms 6,944 KB
testcase_73	AC	917 ms 6,940 KB
testcase_74	AC	265 ms 6,940 KB
testcase_75	AC	2 ms 6,940 KB
testcase_76	AC	2 ms 6,940 KB
testcase_77	AC	3 ms 6,944 KB
testcase_78	AC	2 ms 6,944 KB
testcase_79	AC	114 ms 6,940 KB
testcase_80	AC	12 ms 6,940 KB
testcase_81	AC	12 ms 6,940 KB
testcase_82	AC	13 ms 6,944 KB
testcase_83	AC	35 ms 6,940 KB
testcase_84	AC	35 ms 6,940 KB
testcase_85	AC	41 ms 6,940 KB
testcase_86	AC	41 ms 6,944 KB
testcase_87	AC	49 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#define rep(i,n) for(int i=0; i<(n); i++)


const i64 INF = 1001001001001001001;

pair<vector<i64>,vector<int>> dense_dijkstra(const vector<vector<i64>>& E, const vector<i64>& P, int s){
  int n = E.size();
  vector<i64> D(n, INF);
  D[s] = 0;
  vector<int> pre(n, -1);
  vector<int> visited(n, 0);
  int p = s;
  while(p != -1){
    visited[p] = 1;
    for(int e=0; e<n; e++) if(D[e] > D[p] + P[p] - P[e] + E[p][e]){
      pre[e] = p;
      D[e] = D[p] + P[p] - P[e] + E[p][e];
    }
    int nx = -1;
    i64 nxd = INF;
    for(int e=0; e<n; e++) if(visited[e] == 0) if(D[e] < nxd){ nx = e; nxd = D[nx]; }
    p = nx;
  }
  return make_pair(move(D), move(pre));
}


vector<int> assignment_problem(const vector<vector<i64>>& A){
  int n = A.size();
  vector<vector<i64>> E(n*2+2, vector<i64>(n*2+2,INF));
  rep(i,n) E[n*2][i] = 0;
  rep(i,n) E[n+i][n*2+1] = 0;
  rep(i,n){
    i64 mina = INF;
    rep(j,n) mina = min(mina, A[i][j]);
    rep(j,n) E[i][n+j] = A[i][j] - mina;
  }
  vector<int> ans(n,-1);
  vector<i64> P(n*2+2,0);
  rep(t,n){
    vector<i64> D;
    vector<int> pre;
    tie(D,pre) = dense_dijkstra(E,P,n*2);
    rep(i,n*2+2) P[i] += D[i];
    int p = n*2+1;
    while(p != n*2){
      E[p][pre[p]] = -E[pre[p]][p];
      E[pre[p]][p] = INF;
      if(pre[p] < n) ans[pre[p]] = p-n;
      p = pre[p];
    }
  }
  return ans;
}


int small_N;
vector<vector<int>> small_E;
vector<vector<int>> small_E_idx;
vector<vector<int>> small_E_for_E;
vector<pair<int,int>> small_edges;
int N;
vector<vector<int>> E;
vector<int> bfsorder;
vector<int> parent;
vector<vector<int>> dp;
int ans;


int update_dp(int p){
    int res = -1;
    rep(sp, small_N){
        if(E[p].size() < small_E[sp].size()) continue;
        int assignment_N = E[p].size();
        if(assignment_N < small_E[sp].size()) continue;
        //cout << "assignment_N = " << assignment_N << endl;
        vector<vector<i64>> assignment_matrix(assignment_N, vector<i64>(assignment_N, 0));
        rep(ei, E[p].size()){
            rep(sei, small_E[sp].size()){
                int tmp = dp[E[p][ei]][small_E_idx[sp][sei]];
                assignment_matrix[ei][sei] = ((tmp == -1) ? 1000000000 : -tmp);
            }
        }
        auto assignment_res = assignment_problem(assignment_matrix);
        i64 costsum = 0;
        rep(i, assignment_N) costsum += assignment_matrix[i][assignment_res[i]];
        //cout << "costsum = " << costsum << endl;
        res = max<i64>(res, -costsum);
    }
    rep(se, small_edges.size()){
        for(int e : E[p]) if(dp[e][se] != -1) dp[p][se] = max(dp[p][se], dp[e][se]+1);
        int assignment_N = E[p].size();
        if(assignment_N < small_E_for_E[se].size()) continue;
        //cout << "assignment_N = " << assignment_N << endl;
        vector<vector<i64>> assignment_matrix(assignment_N, vector<i64>(assignment_N, 0));
        rep(ei, E[p].size()){
            rep(sei, small_E_for_E[se].size()){
                int tmp = dp[E[p][ei]][small_E_for_E[se][sei]];
                assignment_matrix[ei][sei] = ((tmp == -1) ? 1000000000 : -tmp);
            }
        }
        auto assignment_res = assignment_problem(assignment_matrix);
        i64 costsum = 0;
        rep(i, assignment_N) costsum += assignment_matrix[i][assignment_res[i]];
        //cout << "costsum = " << costsum << endl;
        dp[p][se] = max<i64>(dp[p][se], -costsum+1);
    }
    rep(se, small_edges.size()){
        for(int e1 : E[p]) for(int e2 : E[p]){
            if(e1 == e2) continue;
            if(dp[e1][se] == -1) continue;
            if(dp[e2][se^1] == -1) continue;
            res = max(res, dp[e1][se] + dp[e2][se^1]);
        }
    }
    return res;
}


int main() {
    cin >> small_N;
    small_E.resize(small_N);
    small_E_idx.resize(small_N);
    rep(i,small_N-1){
        int u,v; cin >> u >> v; u--; v--;
        small_E[u].push_back(v);
        small_E[v].push_back(u);
        small_E_idx[u].push_back(i*2);
        small_E_idx[v].push_back(i*2+1);
        small_edges.push_back(make_pair(u,v));
        small_edges.push_back(make_pair(v,u));
    }

    small_E_for_E.resize(small_edges.size());
    rep(i, small_E_for_E.size()){
        int to = small_edges[i].second;
        for(int ei : small_E_idx[to]) if((ei ^ 1) != i) small_E_for_E[i].push_back(ei);
    }

    cin >> N;
    E.resize(N);
    rep(i,N-1){
        int u,v; cin >> u >> v; u--; v--;
        E[u].push_back(v);
        E[v].push_back(u);
    }

    bfsorder = {0};
    parent.assign(N, -1);
    rep(i,bfsorder.size()){
        int p = bfsorder[i];
        for(int e : E[p]) if(parent[p] != e){
            parent[e] = p;
            bfsorder.push_back(e);
        }
        rep(j,E[p].size()) if(E[p][j] == parent[p]){ swap(E[p][j], E[p].back()); E[p].pop_back(); j--; }
    }

    dp.assign(N, vector<int>((small_N-1)*2, -1));

    //cout << "bfsorder = [ "; for(auto a : bfsorder) cout << a << " "; cout << "]" << endl;

    ans = -1;
    for(int i=N-1; i>=0; i--) ans = max(ans, update_dp(bfsorder[i]));
    cout << ans << endl;
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

yukicoder

結果

テストケース

ソースコード