제출 #107344

#제출 시각아이디문제언어결과실행 시간메모리
107344MohamedAhmed0Bosses (BOI16_bosses)C++14
67 / 100
1543 ms860 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 5005 ; int vis[MAX] , par[MAX]; long long dp[MAX] , cost = 0; vector< vector<int> >adj(MAX) ; int n , cnt = 0 ; void bfs(int src) { queue<int>q ; q.push(src) ; vis[src] = 1 ; par[src] = 0 ; while(!q.empty()) { int node = q.front() ; q.pop() ; cnt++ ; for(auto &child : adj[node]) { if(vis[child] == 1) continue ; vis[child] = 1 ; par[child] = node ; q.push(child) ; } } return ; } void dfs(int node) { for(auto &child : adj[node]) { if(par[child] == node) { dfs(child) ; dp[node] += dp[child] ; } } dp[node]++; cost += dp[node] * 1ll; return ; } int readint() { char c ; c = getchar() ; while(true) { if(c >= '0' && c <= '9') break ; c = getchar() ; } int result = (c - '0') ; c = getchar() ; while(true) { if(c < '0' || c > '9') break ; result = result * 10 + (c - '0') ; c = getchar() ; } return result ; } int main() { n = readint() ; for(int i = 1 ; i <= n ; ++i) { int m ; m = readint() ; while(m--) { int x ; x = readint() ; adj[x].push_back(i) ; } } long long ans = 1e18 ; for(int i = 1 ; i <= n ; ++i) { memset(vis , 0 , sizeof(vis)) ; memset(dp , 0 , sizeof(dp)) ; memset(par , 0 , sizeof(par)) ; cnt = 0 , cost = 0; bfs(i) ; if(cnt != n) continue; dfs(i) ; ans = min(ans , cost) ; } return printf("%lld" , ans) , 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...