Submission #532606

#	Time	Username	Problem	Language	Result	Execution time	Memory
532606		kebine	Bosses (BOI16_bosses)	C++17	100 / 100	632 ms	612 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double db;
#define pairll pair<ll,ll>
#define lpairll pair<pairll,ll>
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define repp(i,a,b) for(ll i = (a); i <= (b); i++)
#define repm(i, a, b) for (ll i = (a); i >= (b); i--)
#define repz(i, a, b) for (ll i = (a); i < (b); i++)
 
const long long MOD = 1e9+7, N = 5e3 + 5, Q = 4e3+5;

ll tc = 1, n, m,k, vis[N], tim = 0, tot = 0, sum = 0;
string s, ye = "YES", no = "NO", nu;
vector<ll> ED[N];

void fastt(){  
  ios_base::sync_with_stdio(0); 
  cin.tie(NULL);
  cout.tie(NULL);  
}

ll dfs(ll idx){
  if(vis[idx] == tim) return 0;
  vis[idx] = tim;
  tot++;
  ll maxd = 0;
  for (auto i : ED[idx]){
    if (vis[i] != tim) maxd += dfs(i);
  }
  //cout << idx << " " << 1+maxd << endl;
  sum += 1+maxd;
  return 1+maxd;  
}

void input(){
  cin >> n;
  repp(i,1,n){
    cin >> m;
    repp(j,1,m) cin >> k, ED[k].pb(i);
  }
} 

void solve(){
  ll ans = 1e18;
  repp(i,1,n){
    repp(j,1,n) vis[j] = -1;
    vis[i] = 1;
    queue<ll> q;
    q.push(i);
    tot = 1;
    sum = 1;
    while(!q.empty()){
      ll tt = q.front();
      q.pop();
      for (auto j : ED[tt]){
        if(vis[j] != -1) continue;
        vis[j] = vis[tt]+1;
        sum += vis[j];
        tot++;
        q.push(j); 
      }
    }
    if(tot != n) continue;
    ans = min(ans,sum);
  }
  cout << ans << endl;
}

int main(){
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
  fastt();
  while(tc--){
    input();
    solve();
  }
}

/*

*/

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33