제출 #693742

#제출 시각아이디문제언어결과실행 시간메모리
693742ajab_01Bosses (BOI16_bosses)C++17
67 / 100
1592 ms1016 KiB
#include<bits/stdc++.h> using namespace std; const int N = 5e3 + 3; const long long INF = 1e18; vector<int> g[N] , vec[N]; deque<int> dq; bool vis[N]; long long ans = INF , val[N]; int n; void bfs(int root){ vis[root] = 1; dq.push_back(root); while(!dq.empty()){ int ver = dq.front(); dq.pop_front(); for(int i : vec[ver]){ if(vis[i]) continue; vis[i] = 1; g[ver].push_back(i); g[i].push_back(ver); dq.push_back(i); } } } void dfs(int ver , int par){ val[ver] = 1; for(int i : g[ver]){ if(i == par) continue; dfs(i , ver); val[ver] += val[i]; } } long long cal(int root){ bfs(root); dfs(root , 0); long long res = 0; bool ch = 1; for(int i = 1 ; i <= n ; i++){ g[i].clear(); res += val[i]; if(!vis[i]) ch = 0; vis[i] = 0; } return (ch ? res : INF); } int main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; for(int i = 1 ; i <= n ; i++){ int x; cin >> x; while(x--){ int j; cin >> j; vec[j].push_back(i); } } for(int i = 1 ; i <= n ; i++) ans = min(ans , cal(i)); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...