結果

問題 No.1789 Tree Growing
ユーザー 👑 NachiaNachia
提出日時 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;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0