Submission #1008540

# Submission time Handle Problem Language Result Execution time Memory
1008540 2024-06-26T14:11:50 Z vjudge1 Bosses (BOI16_bosses) C++17
100 / 100
841 ms 1108 KB
/******************************************************************************
 
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 time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 0 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 6 ms 856 KB Output is correct
13 Correct 3 ms 948 KB Output is correct
14 Correct 137 ms 880 KB Output is correct
15 Correct 31 ms 1108 KB Output is correct
16 Correct 519 ms 860 KB Output is correct
17 Correct 841 ms 944 KB Output is correct
18 Correct 824 ms 860 KB Output is correct