제출 #958400

#제출 시각아이디문제언어결과실행 시간메모리
958400IsaLBosses (BOI16_bosses)C++17
0 / 100
1 ms600 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long #define fi first #define se second #define pii pair<int, int> #define pll pair<ll, ll> const int N = 5069; const ll mod = 1e9 + 7; int tc; int n, sub[N], cn, tot, dp[N]; bool vis[N]; vector<int> al[N]; void dfs(int x) { sub[x] = 1; for(auto z : al[x]) { if(dp[z] == 1 + dp[x]) { dfs(z); sub[x] += sub[z]; } } tot += sub[x]; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int i, j; cin >> n; for(i = 1; i <= n; i++) { int k; cin >> k; for(j = 1; j <= k; j++) { int x; cin >> x; al[x].push_back(i); } } int ans = 1e18; for(i = 1; i <= n; i++) { cn = tot = 0; for(j = 1; j <= n; j++) { sub[j] = 0; vis[j] = 0; dp[j] = 0; } queue<int> q; q.push(i); dp[i] = 1; cn = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(auto z : al[x]) { if(dp[z] == 0) { dp[z] = dp[x] + 1; ++cn; q.push(z); } } } if(cn == n) { dfs(i); ans = min(ans, tot); } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...