oj.uz

Submission #489596

# Submission time Handle Problem Language Result Execution time Memory
489596 2021-11-23T10:22:20 Z SlavicG Bosses (BOI16_bosses) C++17
100 / 100
 1311 ms 948 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 5005;
bool vis[N];
vector<int> adj[N];
vector<int> g[N];
int c[N];
int f = 0;
void bfs(int u){
    forn(i, N)g[i].clear(), vis[i] = false;
    vis[u] = true;

    queue<int> q;
    q.push(u);
    vis[u] = true;

    while(!q.empty()){
        int i = q.front();
        q.pop();

        for(int v: adj[i]){
            if(!vis[v]){
                q.push(v);
                g[i].pb(v);
                vis[v] = true;
            }
        }
    }
}

void dfs(int u, int par){
    ll s = 0;
    for(int v: g[u]){
        if(v == par)continue;
        dfs(v, u);
        s += c[v];
    }
    c[u] = s + 1;
    f += c[u];
}
void solve()
{ 
    int n;
    cin >> n;
    for(int i = 0;i < n; ++i){
        int k;
        cin >> k;
        while(k--){
            int a;
            cin >> a;
            --a;
            adj[a].pb(i);
        }
    }

    int ans = INT_MAX;
    for(int i = 0;i < n; ++i){
        bfs(i);
        bool ok = true;
        for(int j = 0;j < n; ++j){
            if(!vis[j])ok = false;
        }
        if(!ok)continue;
        f = 0;
        dfs(i, -1);
        ans = min(ans, f);
    }

    cout << ans << "\n";
}   
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 190 ms 824 KB Output is correct
15 Correct 32 ms 716 KB Output is correct
16 Correct 665 ms 832 KB Output is correct
17 Correct 1284 ms 884 KB Output is correct
18 Correct 1311 ms 948 KB Output is correct