제출 #973859

#제출 시각아이디문제언어결과실행 시간메모리
973859Halym2007Bosses (BOI16_bosses)C++17
100 / 100
933 ms1248 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e3 + 5; #define ll long long #define pb push_back #define sz size() ll n, sub[N], vis[N]; vector <int> v[N], p[N]; void solve (int x, int pr) { sub[x] = 1; for (int i : p[x]) { if (i == pr) continue; solve (i, x); sub[x] += sub[i]; } } ll root(int x) { queue <int> q; for (int i = 1; i <= n; ++i) { vis[i] = 0; sub[i] = 0; p[i].clear(); } q.push(x); vis[x] = 1; while (!q.empty()) { int x = q.front(); q.pop(); for (int i : v[x]) { if (vis[i]) continue; p[x].pb (i); vis[i] = 1; q.push(i); } } for (int i = 1; i <= n; ++i) { if (!vis[i]) return -1; } solve (x, -1); ll ret = 0; for (int i = 1; i <= n; ++i) { ret += sub[i]; } return ret; } int main () { // freopen ("input.txt", "r", stdin); cin >> n; for (int i = 1; i <= n; ++i) { int k; cin >> k; while (k--) { ll x; cin >> x; v[x].pb (i); } } ll jog = 1e18; for (int i = 1; i <= n; ++i) { ll jj = root (i); if (~jj) { jog = min (jog, jj); } } cout << jog; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...