제출 #701001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701001		Behradm	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	468 KiB

bosses

//In The Name Of GOD
#include "bits/stdc++.h"

#define sz(x) ((int) (x).size())

using namespace std;
using LL = long long;

const int N = 5e3 + 5;
vector<int> out[N], g[N];
int sz[N];

void dfs(int u, int p) {
  sz[u] = 1;
  for (int v : g[u]) {
    if (v == p)
      continue;
    dfs(v, u);
    sz[u] += sz[v];
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int u;
      cin >> u, --u;
      out[u].push_back(i);
    }
  }

  long long ans = 3e18;
  for (int u = 0; u < n; u++) {
    for (int i = 0; i < n; i++)
      g[i].clear();
    vector<bool> mk(n, 0);
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
      int v = q.front(); q.pop();
      mk[v] = 1;
      for (int w : out[v]) {
        if (!mk[w]) {
          mk[w] = 1;
          q.push(w);
          g[v].push_back(w);
          g[w].push_back(v);
        }
      }
    }

    memset(sz, 0, sizeof sz);
    dfs(u, -1);
    long long res = 0;
    for (int i = 0; i < n; i++)
      res += sz[i];
    ans = min(ans, res);
  }
  cout << ans << '\n';
  return 0;
}

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