oj.uz

Submission #95022

# Submission time Handle Problem Language Result Execution time Memory
95022 2019-01-26T20:22:00 Z SecretAgent007 Bosses (BOI16_bosses) C++17
100 / 100
 1338 ms 988 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 9223372036854775807

vector<int> tab[5009];

vector<int> Graph[5009];

int t = 0;
int v = 0;

int dfs(int n, int last){
    v++;
    int tot = 0;
    for(int a : Graph[n]){
        if(a != last)
            tot+=dfs(a,n);
    }
    t+=tot+1;
    return tot+1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i<=n; i++){
        int k;
        cin >> k;
        for(int j = 0; j< k; j++){
            int a;
            cin >> a;
            tab[a].push_back(i);
        }
    }
    int tot = INF;
    for(int i = 1; i<= n;i++){
        queue<int> q;
        vector<bool> cost(n+1,false);
        q.push(i);
        cost[i] = true;
        for(int j = 1; j <=n ; j++) Graph[j].clear();
        while(!q.empty()){
            int node = q.front();
            q.pop();
            for(int a : tab[node]){
                if(cost[a]) continue;
                cost[a]=true;
                Graph[node].push_back(a);
                q.push(a);
            }
        }
        t = 0;
        v = 0;
        dfs(i,-1);
        if(v != n) t = INF;
        tot = min(tot, t);
    }
    cout << tot << endl;
}
/*

*/

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 7 ms 760 KB Output is correct
13 Correct 6 ms 760 KB Output is correct
14 Correct 320 ms 900 KB Output is correct
15 Correct 29 ms 760 KB Output is correct
16 Correct 1044 ms 960 KB Output is correct
17 Correct 1316 ms 988 KB Output is correct
18 Correct 1338 ms 948 KB Output is correct