제출 #1316509

#제출 시각아이디문제언어결과실행 시간메모리
1316509danteBosses (BOI16_bosses)C++20
100 / 100
742 ms1036 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e3 + 3; int n; ll val[N]; vector<int> boss[N], G[N]; bool vis[N]; ll dfs(int v, int p = -1){ ll sum = 1; for (auto i : G[v]){ if (i == p) continue; sum += dfs(i, v); } return val[v] = sum; } int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++){ int k; cin >> k; while (k--){ int x; cin >> x; boss[x].push_back(i); } } ll ans = LLONG_MAX; for (int i = 1; i <= n; i++){ for (int j = 1; j <= n; j++) { vis[j] = 0; G[j].clear(); } queue<int> que; que.push(i); vis[i] = 1; int cnt = 1; while (!que.empty()){ int t = que.front(); que.pop(); for (auto x : boss[t]){ if (!vis[x]){ cnt++; G[x].push_back(t); G[t].push_back(x); que.push(x); vis[x] = 1; } } } if (cnt != n) continue; dfs(i); ll can = 0; for (int j = 1; j <= n; j++) can += val[j]; ans = min(can, ans); } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...