oj.uz

Submission #813333

# Submission time Handle Problem Language Result Execution time Memory
813333 2023-08-07T16:07:47 Z akari Bosses (BOI16_bosses) C++14
100 / 100
 843 ms 5540 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
const ll maxn=2e5+2;

int n;
vector<int> adj[maxn];
vector<int> g[6000];
int dp[6000];
int ans=INT_MAX;
int sum,cnt;


void dfs(int u){
    //cout<<u<<endl;
    dp[u]=1;
    ++cnt;
    for (int v: g[u]){
        dfs(v);
        dp[u]+=dp[v];
    }
    sum+=dp[u];
}

void bfs(int s){
    bool ok[n+3]={};
    queue<int> q;
    q.push(s);
    ok[s]=1;
    for (int i=1;i<=n;++i) g[i].clear();
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int v: adj[u]){
            if (!ok[v]){
                ok[v]=1;
                q.push(v);
                g[u].push_back(v);
            }
        }
    }
    sum=cnt=0;
    /*for (int i=1;i<=n;++i){
        for (int j: g[i]) cout<<j<<" "; cout<<endl;
    }*/
    dfs(s);
    //cout<<endl;
    //cout<<s<<" "<<sum<<endl;    
    if (cnt==n) ans=min(ans,sum);
}



int main(){
    cin>>n;
    for (int i=1;i<=n;++i){
        int k; cin>>k;
        while (k--){
            int x; cin>>x;
            adj[x].push_back(i);
            //cout<<x<<" "<<i<<endl;
        }
    }
    //bfs(1);
    //cout<<endl;
    for (int i=1;i<=n;++i) bfs(i);
    cout<<ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 2 ms 5076 KB Output is correct
3 Correct 2 ms 5024 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 2 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 2 ms 5076 KB Output is correct
12 Correct 6 ms 5204 KB Output is correct
13 Correct 5 ms 5204 KB Output is correct
14 Correct 207 ms 5400 KB Output is correct
15 Correct 21 ms 5360 KB Output is correct
16 Correct 759 ms 5484 KB Output is correct
17 Correct 821 ms 5536 KB Output is correct
18 Correct 843 ms 5540 KB Output is correct