oj.uz

Submission #959559

# Submission time Handle Problem Language Result Execution time Memory
959559 2024-04-08T12:40:07 Z SuPythony Bosses (BOI16_bosses) C++17
100 / 100
 964 ms 1092 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<int>> al(5001, vector<int>()), al2;
vector<ll> sub;

void dfs(int i) {
    if (al2[i].empty()) return;
    for (int v: al2[i]) {
        dfs(v);
        sub[i]+=sub[v];
    }
}

int main() {
    int n; cin>>n;
    for (int i=1; i<=n; i++) {
        int k; cin>>k;
        while (k--) {
            int v; cin>>v;
            al[v].push_back(i);
        }
    }
    ll ans=1e18;
    for (int i=1; i<=n; i++) {
        sub.assign(n+1,1);
        al2.assign(n+1, vector<int>());
        vector<int> vis(n+1,0);
        queue<int> q;
        q.push(i);
        vis[i]=1;
        int nvis=1;
        while (!q.empty()) {
            int u=q.front(); q.pop();
            for (int v: al[u]) {
                if (vis[v]) continue;
                vis[v]=1;
                nvis++;
                al2[u].push_back(v);
                q.push(v);
            }
        }
        if (nvis<n) continue;
        dfs(i);
        ll s=0;
        for (int i=1; i<=n; i++) s+=sub[i];
        ans=min(ans,s);
    }
    cout<<ans;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 6 ms 636 KB Output is correct
13 Correct 5 ms 604 KB Output is correct
14 Correct 172 ms 920 KB Output is correct
15 Correct 88 ms 856 KB Output is correct
16 Correct 549 ms 860 KB Output is correct
17 Correct 933 ms 1084 KB Output is correct
18 Correct 964 ms 1092 KB Output is correct