제출 #1201822

#제출 시각아이디문제언어결과실행 시간메모리
1201822waigoonBosses (BOI16_bosses)C++20
67 / 100
1595 ms1204 KiB
#include <bits/stdc++.h> #define int long long #define float long double #define pii pair<int, int> #define tii tuple<int, int, int> #define f first #define s second #define ve vector #define emb emplace_back #define em emplace using namespace std; const int inf = 1e18; const int mod = 1e9 + 7; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; ve<ve<int>> inv(n); for (int i = 0; i < n; i++) { int k; cin >> k; while (k--) { int x; cin >> x; inv[x-1].emb(i); } } function<int(int, int, ve<ve<int>>&, ve<int>&)> dfs = [&](int x, int par, ve<ve<int>>& adj, ve<int>& val) { int sum = 0; for (auto e : adj[x]) if (e != par) sum += dfs(e, x, adj, val); return val[x] = sum + 1; }; int mn = inf; for (int i = 0; i < n; i++) { queue<pii> q; ve<bool> vis(n, false); ve<ve<int>> adj(n); q.em(i, -1), vis[i] = true; int cnt = 1; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (auto e : inv[x]) { if (e == y || vis[e]) continue; adj[x].emb(e), vis[e] = true, cnt++, q.em(e, x); } } if (cnt != n) continue; ve<int> val(n); dfs(i, -1, adj, val); int sum = 0; for (auto e : val) sum += e; mn = min(mn, sum); } cout << mn; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...