제출 #978205

#제출 시각아이디문제언어결과실행 시간메모리
978205AmaarsaaBosses (BOI16_bosses)C++14
100 / 100
863 ms1148 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long ; vector < ll > adj[5002], ad[5003]; ll n; ll C[5003]; void Dfs(ll x) { for ( ll X : ad[x]) { Dfs(X); C[x] += C[X]; } } ll Go(ll x) { ll i, node; queue < ll > q; ll D[5003], cnt = 1; for (i = 1; i <= n; i ++) D[i] = -1, C[i] = 1, ad[i].clear(); q.push(x); D[x] = 0; while(!q.empty()) { node= q.front(); q.pop(); for ( ll child : adj[node] ) { if ( D[child] == -1) { q.push(child); ad[node].push_back(child); cnt ++; D[child] = 1; } } } if ( cnt != n) return -1; Dfs(x); ll s = 0; for ( i = 1; i <= n; i ++) s += C[i]; return s; } int main() { // freopen("moocast.in", "r", stdin); // freopen("moocast.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(NULL); ll i, j, x, m, s, ans; cin >> n; for (i = 1; i <= n; i ++) { cin >> m; for (j = 1; j <= m; j ++) { cin >> x; adj[x].push_back(i); } } ans = LONG_LONG_MAX; for (i = 1; i <= n; i ++) { s = Go(i); if ( s != -1) ans= min(ans, s); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...