제출 #532591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532591		kebine	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	460 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;
  memset(vis,0,sizeof(vis));
  repp(i,1,n){
    //cout << "i = " << i << endl;
    tim++;
    tot = 0, sum = 0;
    dfs(i);
    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: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33