Facebook
From emanlaicepsa, 1 Month ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 35
  1. //by emanlaicepsa
  2. #include<bits/stdc++.h>
  3. #define ll long long
  4. #define int ll
  5. #define IOS ios::sync_with_stdio(0),cin.tie(0);
  6. #define pb push_back
  7. #define pii pair<int,int>
  8. #define fi first
  9. #define se second
  10. #define all(n) (n).begin(),(n).end()
  11. #define mem(n,k) memset(n,k,sizeof(n))
  12. using namespace std;
  13.  
  14. bool in[2505][55];
  15. ll dp[2505][55], cnt[2505];
  16. vector<int> arr[55];
  17.  
  18. void solve(int n){
  19.         mem(in,0);
  20.         mem(dp,0x3f);
  21.         mem(cnt,0);
  22.         vector<int> tot;
  23.        
  24.         for(int i=1,x;i<=n;i++){
  25.                 cin>>x;
  26.                 arr[i].resize(x);
  27.                 for(int j=0;j<x;j++){
  28.                         cin>>arr[i][j];
  29.                         tot.pb(arr[i][j]);
  30.                 }
  31.         }
  32.         sort(all(tot));
  33.         tot.resize(unique(all(tot))-tot.begin());
  34.        
  35.         for(int i=1;i<=n;i++){
  36.                 for(int j=0,x=arr[i].size();j<x;j++){
  37.                         arr[i][j] = lower_bound(all(tot),arr[i][j]) - tot.begin() + 1;
  38.                         in[arr[i][j]][i] = 1;
  39.                         //cout<<arr[i][j]<<" \n"[j==x-1];
  40.                 }
  41.         }
  42.        
  43.         int siz = tot.size();
  44.        
  45.        
  46.        
  47.         for(int i=1;i<=siz;i++){
  48.                 for(int j=1;j<=n;j++){
  49.                         cnt[i] += in[i][j];
  50.                 }
  51.         }
  52.        
  53.         for(int i=1;i<=n;i++){
  54.                 if(in[siz][i]) dp[siz][i] = cnt[siz];
  55.         }
  56.         //for(int i=1;i<=n;i++) cout<<dp[siz][i]<<" \n"[i==n];
  57.        
  58.         for(int i=siz-1;i>=1;i--){
  59.                 for(int j=1;j<=n;j++){
  60.                         if(!in[i][j]) continue;
  61.                         for(int k=1;k<=n;k++){
  62.                                 if(dp[i+1][k] > 1e9) continue;
  63.                                 dp[i][j] = min(dp[i][j],dp[i+1][k]+cnt[i]);
  64.                                 if(in[i][k] && k!=j) dp[i][j] = min(dp[i][j],dp[i+1][k]+cnt[i]-1);
  65.                                 if(cnt[i]==1 && k==j) dp[i][j] = min(dp[i][j],dp[i+1][k]);
  66.                         }
  67.                         //cout<<i<<" "<<j<<" "<<dp[i][j]<<'\n';
  68.                 }
  69.         }
  70.         ll ans = 1e18;
  71.         for(int i=1;i<=n;i++){
  72.                 ans = min(ans,dp[1][i]);
  73.         }
  74.         cout<<ans*2-n-1<<'\n';
  75. }
  76.  
  77. signed main(){
  78.         IOS;
  79.         int cnt = 0, x;
  80.         while(cin>>x){
  81.                 cout<<"Case "<<++cnt<<": ";
  82.                 solve(x);
  83.         }
  84. }
  85.