結果
問題 | No.1789 Tree Growing |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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;