제출 #107345

#제출 시각아이디문제언어결과실행 시간메모리
107345MohamedAhmed0Bosses (BOI16_bosses)C++14
67 / 100
1552 ms98812 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 5005 ; int vis[MAX] , par[MAX][MAX] , can[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] = src ; par[src][src] = 0 ; while(!q.empty()) { int node = q.front() ; q.pop() ; cnt++ ; for(auto &child : adj[node]) { if(vis[child] == src) continue ; vis[child] = src ; par[src][child] = node ; q.push(child) ; } } return ; } int src ; void dfs(int node) { for(auto &child : adj[node]) { if(par[src][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) { cnt = 0 ; bfs(i) ; if(cnt == n) can[i] = 1 ; } for(int i = 1 ; i <= n ; ++i) { if(can[i] == 0) continue ; memset(dp , 0 , sizeof(dp)) ; src = i ; cnt = 0 , cost = 0; 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...