oj.uz

Submission #489592

# Submission time Handle Problem Language Result Execution time Memory
489592 2021-11-23T10:18:28 Z SlavicG Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1040 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];
ll c[N];
ll 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);
        }
    }

    ll ans = LLONG_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 1 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 1 ms 552 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 1 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 1 ms 552 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 1 ms 556 KB Output is correct

Subtask #3
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 1 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 1 ms 552 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 1 ms 556 KB Output is correct
12 Correct 6 ms 716 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 292 ms 1040 KB Output is correct
15 Correct 33 ms 836 KB Output is correct
16 Correct 888 ms 940 KB Output is correct
17 Execution timed out 1591 ms 972 KB Time limit exceeded
18 Halted 0 ms 0 KB -