oj.uz

Submission #489594

# Submission time Handle Problem Language Result Execution time Memory
489594 2021-11-23T10:21:48 Z SlavicG Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 996 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[v].pb(i);
                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 1 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 1 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 1 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 1 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 2 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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 2 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 6 ms 588 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 312 ms 996 KB Output is correct
15 Correct 32 ms 796 KB Output is correct
16 Correct 889 ms 880 KB Output is correct
17 Execution timed out 1582 ms 844 KB Time limit exceeded
18 Halted 0 ms 0 KB -