oj.uz

Submission #350637

# Submission time Handle Problem Language Result Execution time Memory
350637 2021-01-19T07:09:09 Z Hossein29 Bosses (BOI16_bosses) C++17
100 / 100
 1479 ms 1048 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e3+10;
const int inf = 1e9+1;

int n,ans,sum,sz;
bool check;
vector<int>G[maxn];
vector<int>H[maxn];
bool marked[maxn];
int val[maxn];

void bfs(int v){
    marked[v] = true;
    queue<int>q;
    q.push(v);
    while(!q.empty()){
        int p = q.front();
        q.pop();
        sz++;
        H[p].clear();
        for(int b : G[p]){
            if(marked[b]) continue;
            marked[b] = true;
            q.push(b);
            H[p].push_back(b);
        }
    }
}

void dfs(int v){
    int s = 0;
    sz++;
    for(int b : H[v]){
        dfs(b);
        s += val[b];
    }
    val[v] = s + 1;
    sum += val[v];
    if(ans <= sum){
        check = false;
        return;
    }
}

int32_t main(){
    ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
    ////////////////////////////////////////////////
    ans = inf;
    sum = 0;
    cin >> n;
    for(int i = 0;i<n;i++){
        int x; cin >> x;
        for(int j = 0;j<x;j++){
            int y; cin >> y;
            G[y].push_back(i+1);
        }
    }
    for(int i = 0;i<n;i++){
        fill(marked,marked+n+1,false);
        sz = 0;
        bfs(i+1);
        if(sz != n){
            continue;
        }
        check = true;
        sum = 0;
        sz = 0;
        dfs(i+1);
        if(check == true && sz == n){
            ans = min(ans,sum);
        }
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 8 ms 748 KB Output is correct
13 Correct 4 ms 748 KB Output is correct
14 Correct 172 ms 1004 KB Output is correct
15 Correct 20 ms 880 KB Output is correct
16 Correct 765 ms 976 KB Output is correct
17 Correct 1454 ms 1044 KB Output is correct
18 Correct 1479 ms 1048 KB Output is correct