結果
問題 |
No.1789 Tree Growing
|
ユーザー |
![]() |
提出日時 | 2021-12-18 19:48:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 5,000 ms |
コード長 | 4,358 bytes |
コンパイル時間 | 6,542 ms |
コンパイル使用メモリ | 291,608 KB |
最終ジャッジ日時 | 2025-01-27 03:22:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 85 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; using ll=long long; const int MAXN=100; const int MAXK=100; const int INF=1e6; int n, k, vn[MAXN][MAXN], vk[MAXK], ordn[MAXN][MAXN], ordk[MAXK]; vector<int> gn[MAXN], gk[MAXK]; int main() { cin>>k; for(int i=0; i<k-1; i++){ int a, b; cin>>a>>b; a--; b--; gk[a].push_back(b); gk[b].push_back(a); } cin>>n; for(int i=0; i<n-1; i++){ int a, b; cin>>a>>b; a--; b--; gn[a].push_back(b); gn[b].push_back(a); } { queue<int> que; que.push(0); bool used[MAXK]={}; used[0]=1; int t=0; while(!que.empty()){ int x=que.front(); que.pop(); ordk[x]=t; vk[t++]=x; for(auto y:gk[x]){ if(used[y]) continue; que.push(y); used[y]=1; } } } string ts[MAXK]; int tk[MAXK]; vector<string> vss(k); for(int i=k-1; i>=0; i--){ int x=vk[i]; vector<string> vs; for(auto y:gk[x]){ if(ordk[y]<ordk[x]) continue; vs.push_back("("+ts[ordk[y]]+")"); } sort(vs.begin(), vs.end()); ts[i]=""; for(auto s:vs) ts[i]+=s; vss[i]=ts[i]; } sort(vss.begin(), vss.end()); vss.erase(unique(vss.begin(), vss.end()), vss.end()); for(int i=0; i<k; i++){ tk[i]=lower_bound(vss.begin(), vss.end(), ts[i])-vss.begin(); } vector<string> vss2; string tsn[MAXN][MAXN]; int tn[MAXN][MAXN]; for(int r=0; r<n; r++){ queue<int> que; que.push(r); bool used[MAXN]={}; used[r]=1; int t=0; while(!que.empty()){ int x=que.front(); que.pop(); ordn[r][x]=t; vn[r][t++]=x; for(auto y:gn[x]){ if(used[y]) continue; que.push(y); used[y]=1; } } for(int i=n-1; i>=0; i--){ int x=vn[r][i]; vector<string> vs; for(auto y:gn[x]){ if(ordn[r][y]<ordn[r][x]) continue; vs.push_back("("+tsn[r][ordn[r][y]]+")"); } sort(vs.begin(), vs.end()); tsn[r][i]=""; for(auto s:vs) tsn[r][i]+=s; vss2.push_back(tsn[r][i]); } } sort(vss2.begin(), vss2.end()); vss2.erase(unique(vss2.begin(), vss2.end()), vss2.end()); for(int r=0; r<n; r++){ for(int i=0; i<n; i++){ tn[r][i]=lower_bound(vss2.begin(), vss2.end(), tsn[r][i])-vss2.begin(); } } vector<vector<int>> dp(vss.size(), vector<int>(vss2.size(), -INF)); vector<vector<bool>> ok(vss.size(), vector<bool>(vss2.size())); int ans=-INF; for(int r=0; r<n; r++){ for(int i=n-1; i>=0; i--){ for(int j=k-1; j>=0; j--){ if(!(i==0 && j==0) && ok[tk[j]][tn[r][i]]) continue; int x=vn[r][i], y=vk[j], j1=tk[j], i1=tn[r][i]; ok[j1][i1]=1; for(auto z:gn[x]){ if(ordn[r][z]<ordn[r][x]) continue; dp[j1][i1]=max(dp[j1][i1], dp[j1][tn[r][ordn[r][z]]]+1); } int n1=gn[vn[r][i]].size(), k1=gk[vk[j]].size(); if(i>0) n1--; if(j>0) k1--; if(k1>n1) continue; mcf_graph<int, int> g(k1+n1+2); int s=k1+n1, t=s+1; for(int l=0; l<k1; l++) g.add_edge(s, l, 1, 0); for(int l=0; l<n1; l++) g.add_edge(l+k1, t, 1, 0); int i2=0; for(auto z:gn[x]){ if(ordn[r][z]<ordn[r][x]) continue; int j2=0; for(auto w:gk[y]){ if(ordk[w]<ordk[y]) continue; g.add_edge(j2, i2+k1, 1, INF-dp[tk[ordk[w]]][tn[r][ordn[r][z]]]); j2++; } i2++; } auto res=g.flow(s, t); if(res.first==k1){ if(i==0 && j==0) ans=max(ans, INF*k1-res.second); dp[j1][i1]=max(dp[j1][i1], INF*k1-res.second); } } } } if(ans<0){ cout<<-1<<endl; return 0; } ans+=k-1; cout<<ans<<endl; return 0; }