結果
問題 |
No.1789 Tree Growing
|
ユーザー |
![]() |
提出日時 | 2021-12-18 21:37:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,955 bytes |
コンパイル時間 | 3,262 ms |
コンパイル使用メモリ | 241,044 KB |
最終ジャッジ日時 | 2025-01-27 03:28:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 82 TLE * 3 |
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-function" #define private public #include<atcoder/all> #undef private #pragma GCC diagnostic pop using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) { a = max(a, b); } template<class T> void chmin(T& a, const T& b) { a = min(a, b); } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; int n1, n2; VI g1[110], g2[110]; void dfs1(int u, int p); void dfs2(int u, int p); vector<vector<int>> dp[110][110]; void Rerooting() { dfs1(0, -1); dfs2(0, -1); } mcf_graph<int, int> G; VVI calc_val(int u, int i) { const int v = g2[u][i]; VVI d(n1); auto dfs = [&](auto&& self, int x, int p) -> void { d[x].resize(g1[x].size()); int j = 0; for(int y : g1[x]) { // edge (x, j) if (y != p) self(self, y, x); // match u->v and x->y int mx = -1; // skip case for(int k = 0, sz = g2[v].size(); k < sz; k++) { int w = g2[v][k]; if (w == u) continue; // v -> w int temp = dp[v][k][x][j]; if (temp != -1) chmax(mx, temp + 1); } // put case // u->'v' x->'y' int sz1 = g1[y].size(); int sz2 = g2[v].size(); if (sz1 <= sz2) { int s = sz1 + sz2, t = s + 1; // mcf_graph<int, int> g(t + 1); { G._n = t + 1; G._edges.clear(); } constexpr int B = 110; rep(i, sz1) rep(j, sz2) { int z = g1[y][i], w = g2[v][j]; if (z == x || w == u) continue; int temp = dp[v][j][y][i]; if (temp == -1) continue; G.add_edge(i, sz1 + j, 1, B - temp); } rep(i, sz1) G.add_edge(s, i, 1, 0); rep(j, sz2) G.add_edge(sz1 + j, t, 1, 0); auto [f, cost] = G.flow(s, t); if (f == sz1 - 1) { cost -= f * B; cost = -cost; chmax(mx, cost + 1); } } d[x][j++] = mx; } }; dfs(dfs, 0, -1); return d; } void dfs1(int u, int p=-1) { const int sz2 = g2[u].size(); // dp[u].resize(sz2); for(int i = 0; i < sz2; i++) { int v = g2[u][i]; if (v == p) continue; dfs1(v, u); // cout << u << "->" << v << "(" << i << ")" << endl; dp[u][i] = calc_val(u, i); } return; } void dfs2(int u, int p=-1) { const int sz = g2[u].size(); for(int i = 0; i < sz; i++) { int v = g2[u][i]; if (v == p) continue; const int sz_v = g2[v].size(); for(int j = 0; j < sz_v; j++) { const int w = g2[v][j]; if (w != u) continue; // dp[v][j] = sl[u][i].merge(sr[u][i + 1]).apply(e); dp[v][j] = calc_val(v, j); break; } dfs2(v, u); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); rep(_, 2) { cin >> n1; // g1.resize(n1); rep(_, n1 - 1) { int a, b; cin >> a >> b; a--, b--; g1[a].emplace_back(b); g1[b].emplace_back(a); } swap(n1, n2); swap(g1, g2); } Rerooting(); int ans = -1; rep(x, n1) rep(u, n2) { int sz1 = g1[x].size(), sz2 = g2[u].size(); if (sz1 > sz2) continue; int s = sz1 + sz2, t = s + 1; // mcf_graph<int, int> g(t + 1); { G._n = t + 1; G._edges.clear(); } constexpr int B = 110; rep(i, sz1) rep(j, sz2) { int temp = dp[u][j][x][i]; if (temp != -1) G.add_edge(i, sz1 + j, 1, B - temp); } rep(i, sz1) G.add_edge(s, i, 1, 0); rep(j, sz2) G.add_edge(sz1 + j, t, 1, 0); auto [f, cost] = G.flow(s, t); if (f == sz1) { cost -= f * B; cost = -cost; chmax(ans, cost); } } cout << ans << endl; }