oj.uz

Submission #516163

# Submission time Handle Problem Language Result Execution time Memory
516163 2022-01-20T14:15:17 Z perchuts Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1172 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[j].clear();
            assigned[j] = 0;
        }
        tmp = 0;
    }
    cout<<ans<<endl;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 796 KB Output is correct
4 Correct 0 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 776 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 792 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 5 ms 932 KB Output is correct
13 Correct 4 ms 924 KB Output is correct
14 Correct 258 ms 1116 KB Output is correct
15 Correct 22 ms 1040 KB Output is correct
16 Correct 838 ms 1172 KB Output is correct
17 Execution timed out 1593 ms 1100 KB Time limit exceeded
18 Halted 0 ms 0 KB -