제출 #1251304

#제출 시각아이디문제언어결과실행 시간메모리
1251304IsamBosses (BOI16_bosses)C++20
0 / 100
200 ms327680 KiB

#include <bits/stdc++.h>
using namespace std;

#define intt long long

constexpr int sz = 5005;
constexpr intt inf = 1e18 + 7;

int n, cnt;
intt cost, ans = inf;
vector<int> g[sz], gm[sz];
bitset<sz> vis;

void bfs(int root){
  queue<int> q;
  q.push(root);
  vis[root] = 1;
  while(!q.empty()){
    int cur = q.front();
    q.pop();
    ++cnt;
    for(int &u : g[cur]){
      if(vis[u]) continue;
      vis[u] = 1;
      q.push(u);
      gm[cur].emplace_back(u);
    }
  }
}



intt dfs(int u){
  intt res = 1;
  for(auto to : gm[u]) res += dfs(to);
  cost += res;
  return res;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  for(int i = 1, k; i <= n; ++i){
    cin >> k;
    for(int j = 1, u; j <= k; ++j){
      cin >> u;
      g[u].emplace_back(i);
    }
  }
  for(int i = 1; i <= n; ++i){
    vis.reset();
    cost = 0ll;
    cnt = 0;
    bfs(i);
    if(cnt ^ n) continue; 
    dfs(i);
    for(int j = 1; j <= n; ++j) gm[j].clear();
    ans = min(ans, cost);
  }
  cout << ans << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...