結果

問題 No.1789 Tree Growing
ユーザー 👑 Nachia
提出日時 2021-12-18 00:52:30
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,689 ms / 5,000 ms
コード長 5,371 bytes
コンパイル時間 5,477 ms
コンパイル使用メモリ 138,872 KB
最終ジャッジ日時 2025-01-27 02:55:29
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
0