oj.uz

Submission #516157

# Submission time Handle Problem Language Result Execution time Memory
516157 2022-01-20T13:27:55 Z perchuts Bosses (BOI16_bosses) C++17
0 / 100
 1 ms 792 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<int>can[10001];
vector<int>g[10001];
bool assigned[10001];
int n;

bool createTree(int root){
    queue<int>q;
    q.push(root);
    int qtd = 0;
    while(!q.empty()){
        qtd++;
        int u = q.front();
        q.pop();
        for(auto v:can[u]){
            if(!assigned[v]){
                assigned[v] = 1;
                g[v].pb(u);
                g[u].pb(v);
                q.push(v);
            }
        }
    }
    return qtd==n;
}

int tmp;

int compute(int u,int p){
    int salary = 1;
    for(auto v:g[u]){
        if(v==p)continue;
        salary+=compute(v,u);
    }
    tmp+=salary;
    return salary;
}

int main(){_
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        for(int j=1;j<=k;j++){
            int x;cin>>x;
            can[x].pb(i);
        }
    }   
    int ans = inf; 
    for(int i=1;i<=n;i++){
        assigned[i] = 1;
        if(createTree(i)){
            compute(i,i);
            ckmin(ans,tmp);
        }
        for(int j=1;j<=n;j++){
            g[i].clear();
            assigned[i] = 0;
        }
        tmp = 0;
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 792 KB Output is correct
2 Incorrect 1 ms 788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 792 KB Output is correct
2 Incorrect 1 ms 788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 792 KB Output is correct
2 Incorrect 1 ms 788 KB Output isn't correct
3 Halted 0 ms 0 KB -