結果
問題 | No.1789 Tree Growing |
ユーザー |
![]() |
提出日時 | 2021-12-10 02:50:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 74 ms / 5,000 ms |
コード長 | 7,367 bytes |
コンパイル時間 | 4,180 ms |
コンパイル使用メモリ | 205,952 KB |
最終ジャッジ日時 | 2025-01-26 07:24:42 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 85 |
コンパイルメッセージ
main.cpp: In member function ‘void hungarian<T>::augment() [with T = long long int]’: main.cpp:90:25: warning: ‘y’ may be used uninitialized [-Wmaybe-uninitialized] 90 | if(y<m) break; | ^~ main.cpp:76:24: note: ‘y’ was declared here 76 | int x, y; | ^ main.cpp:108:51: warning: ‘x’ may be used uninitialized [-Wmaybe-uninitialized] 108 | for(int cx=x, cy=y, ty; cx!=-2; cx=prev[cx], cy=ty){ | ~~^~~~ main.cpp:76:21: note: ‘x’ was declared here 76 | int x, y; | ^
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#include <list>#include <atcoder/all>#define popcount __builtin_popcountusing namespace std;using namespace atcoder;typedef long long ll;typedef pair<int, int> P;template<typename T>struct hungarian{//n<=mconst T inf=numeric_limits<T>::max();int n, m, max_match, root;T max_cost;vector<vector<T>> cost;vector<T> lx, ly, slack;vector<int> xy, yx, prev, slackx;vector<bool> s, t;void update_labels(){T delta=inf;for(int y=0; y<m; y++) if(!t[y]) delta=min(delta, slack[y]);for(int x=0; x<n; x++) if(s[x]) lx[x]-=delta;for(int y=0; y<m; y++) if(t[y]) ly[y]+=delta;for(int y=0; y<m; y++) if(!t[y]) slack[y]-=delta;}void add_to_tree(int x, int prevx){s[x]=true;prev[x]=prevx;for(int y=0; y<m; y++){if(lx[x]+ly[y]-cost[x][y]<slack[y]){slack[y]=lx[x]+ly[y]-cost[x][y];slackx[y]=x;}}}void augment(){if(max_match==n) return;fill(s.begin(), s.end(), false);fill(t.begin(), t.end(), false);fill(prev.begin(), prev.end(), -1);queue<int> que;for(int x=0; x<n; x++){if(xy[x]==-1){root=x;que.push(x);prev[x]=-2;s[x]=true;break;}}for(int y=0; y<m; y++){slack[y]=lx[root]+ly[y]-cost[root][y];slackx[y]=root;}int x, y;while(1){while(!que.empty()){x=que.front(); que.pop();for(y=0; y<m; y++){if(cost[x][y]==lx[x]+ly[y] && !t[y]){if(yx[y]==-1) break;t[y]=true;que.push(yx[y]);add_to_tree(yx[y], x);}}if(y<m) break;}if(y<m) break;update_labels();for(y=0; y<m; y++){if(!t[y] && slack[y]==0){if(yx[y]==-1){x=slackx[y];break;}else{t[y]=true;que.push(yx[y]);add_to_tree(yx[y], slackx[y]);}}}if(y<m) break;}if(y<m){max_match++;for(int cx=x, cy=y, ty; cx!=-2; cx=prev[cx], cy=ty){ty=xy[cx];yx[cy]=cx, xy[cx]=cy;}augment();}}hungarian(const vector<vector<T>> &cost):max_match(0), max_cost(0), cost(cost), n(cost.size()), m(cost[0].size()), lx(n, -inf), ly(m), xy(n, -1),yx(m, -1), s(n), t(m), prev(n), slack(m), slackx(m){for(int x=0; x<n; x++) for(int y=0; y<m; y++) lx[x]=max(lx[x], cost[x][y]);augment();for(int x=0; x<n; x++) max_cost+=cost[x][xy[x]];}};const int MAXN=100;const int MAXK=100;const ll INF=1e9;int n, k;vector<int> gn[MAXN], gk[MAXK];int vn[MAXN], vk[MAXK], ordn[MAXN], ordk[MAXK];ll dp[MAXN][MAXK], dp2[MAXN][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;}}}{queue<int> que;que.push(0);bool used[MAXN]={};used[0]=1;int t=0;while(!que.empty()){int x=que.front(); que.pop();ordn[x]=t;vn[t++]=x;for(auto y:gn[x]){if(used[y]) continue;que.push(y);used[y]=1;}}}for(int i=0; i<n; i++) for(int j=0; j<k; j++) dp[i][j]=-INF, dp2[i][j]=-INF;for(int i=n-1; i>=0; i--){for(int j=k-1; j>=0; j--){int x=vn[i], y=vk[j];for(auto z:gn[x]){if(ordn[z]<ordn[x]) continue;dp[i][j]=max(dp[i][j], dp[ordn[z]][j]+1);}int n1=gn[x].size(), k1=gk[y].size();if(i>0) n1--;if(j>0) k1--;if(k1>n1) continue;vector<vector<ll>> cost(k1, vector<ll>(n1, -INF));int i1=0;for(auto z:gn[x]){if(ordn[z]<ordn[x]) continue;int j1=0;for(auto w:gk[y]){if(ordk[w]<ordk[y]) continue;cost[j1++][i1]=dp[ordn[z]][ordk[w]];}i1++;}ll mx=0;if(k1){hungarian<ll> h(cost);mx=h.max_cost;}dp[i][j]=max(dp[i][j], mx);}}ll ans=-INF;for(int i=0; i<n; i++){for(int j=0; j<k; j++){int x=vn[i], y=vk[j];set<pair<ll, int>> st;st.insert({-INF, -1});for(auto z:gn[x]){if(ordn[z]<ordn[x]){st.insert({dp2[i][j]+1, z});}else{st.insert({dp[ordn[z]][j]+1, z});}}for(auto z:gn[x]){if(ordn[z]<ordn[x]) continue;st.erase({dp[ordn[z]][j]+1, z});dp2[ordn[z]][j]=max(dp2[ordn[z]][j], st.rbegin()->first);st.insert({dp[ordn[z]][j]+1, z});}int n1=gn[x].size(), k1=gk[y].size();if(j>0) k1--;if(k1>n1) continue;if(k1==0){for(auto z:gn[x]){if(ordn[z]<ordn[x]) continue;dp2[ordn[z]][j]=max(dp2[ordn[z]][j], 0ll);}continue;}vector<vector<ll>> cost0(k1, vector<ll>(n1, -INF));vector<bool> myon(n1);int i1=0;for(auto z:gn[x]){int j1=0;for(auto w:gk[y]){if(ordk[w]<ordk[y]) continue;if(ordn[z]<ordn[x]){cost0[j1++][i1]=dp2[i][ordk[w]];}else{cost0[j1++][i1]=dp[ordn[z]][ordk[w]];}}i1++;}hungarian<ll> h0(cost0);if(j==0){ans=max(ans, h0.max_cost);}for(int l=0; l<k1; l++){myon[h0.xy[l]]=1;}for(int l=0; l<n1; l++){int z0=gn[x][l];if(ordn[z0]<ordn[x]) continue;if(!myon[l]){dp2[ordn[z0]][j]=max(dp2[ordn[z0]][j], h0.max_cost);continue;}auto cost=cost0;for(int m=0; m<k1; m++) cost[m][l]=-INF;hungarian<ll> h(cost);dp2[ordn[z0]][j]=max(dp2[ordn[z0]][j], h.max_cost);}}}if(ans<0){cout<<-1<<endl;return 0;}ans+=k-1;cout<<ans<<endl;return 0;}