제출 #78541

#제출 시각아이디문제언어결과실행 시간메모리
78541vexBosses (BOI16_bosses)C++14
67 / 100
1551 ms1140 KiB
#include <bits/stdc++.h> #define maxn 5005 using namespace std; int n; vector<int>d[maxn],adj[maxn]; bool bio[maxn]; queue<int>mq; void bfs(int v) { mq.push(v); bio[v]=true; while(!mq.empty()) { int u=mq.front(); mq.pop(); for(auto x:d[u]) { if(bio[x])continue; mq.push(x); bio[x]=true; adj[u].push_back(x); } } } int tre; int dp[maxn]; void dfs(int v) { dp[v]=1; for(auto x:adj[v]) { dfs(x); dp[v]+=dp[x]; } //cout<<dp[v]<<" "; tre+=dp[v]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; for(int j=0;j<x;j++) { int w; cin>>w; d[w].push_back(i); } } /*for(int i=1;i<=n;i++) { cout<<i<<" "<<d[i].size()<<" "; for(auto x:d[i])cout<<x<<" "; cout<<endl; } cout<<endl<<endl;*/ int sol=5*maxn*maxn; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { bio[j]=false; adj[j].clear(); dp[j]=0; } tre=0; bfs(i); bool t=true; for(int j=1;j<=n;j++)if(!bio[j])t=false; if(!t)continue; /*for(int j=1;j<=n;j++) { cout<<j<<" "<<adj[j].size()<<" "; for(auto x:adj[j])cout<<x<<" "; cout<<endl; }*/ dfs(i); //cout<<endl;for(int j=1;j<=n;j++)cout<<dp[j]<<" "; sol=min(tre,sol); /*cout<<tre<<endl; cout<<endl<<endl;*/ } cout<<sol<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...