제출 #1008540

#제출 시각아이디문제언어결과실행 시간메모리
1008540vjudge1Bosses (BOI16_bosses)C++17
100 / 100
841 ms1108 KiB
/****************************************************************************** Welcome to GDB Online. GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl, C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog. Code, Compile, Run and Debug online from anywhere in world. *******************************************************************************/ #include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long vector <int> v[5001],child[5001]; int vis[5001]; int n,k; array <int,2> dfs(int i,int last){ if(child[i].size()==0) return {1,1}; int sum=0,sum2=0; for(int j:child[i]){ if(j!=last){ array <int,2> a=dfs(j,i); sum+=a[0]; sum2+=a[1]; } } return {sum+1,sum2+sum+1}; } int bfs(int i){ for(int i=1;i<=n;i++) child[i].clear(); memset(vis,0,sizeof vis); int CNT=1; queue <int> qu; qu.push(i); vis[i]=1; while(!qu.empty()){ int I=qu.front(); qu.pop(); for(int j:v[I]){ if(vis[j]==0){ vis[j]=1; child[I].push_back(j); CNT++; qu.push(j); } } } if(CNT==n) return dfs(i,0)[1]; else return 1e18; } signed main() { cin>>n; for(int i=1;i<=n;i++){ cin>>k; for(int j=1;j<=k;j++){ int a; cin>>a; v[a].push_back(i); } } int mn=1e18; for(int i=1;i<=n;i++) mn=min(bfs(i),mn); cout<<mn; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...