oj.uz

Submission #262384

# Submission time Handle Problem Language Result Execution time Memory
262384 2020-08-12T18:29:28 Z Hehehe Bosses (BOI16_bosses) C++14
100 / 100
 784 ms 1144 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<long double, long double>
#define sz(x) (int)((x).size())
//#define int long long

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e4 + 11;
const ll INF64 = 2e9;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int n, viz[N], d[N];
vector<int>v[N];

int bfs(int x){

    for(int i = 1; i <= n; i++)viz[i] = 0, d[i] = 0;

    d[x] = 1;
    viz[x] = 1;

    queue<int>q;
    q.push(x);

    while(!q.empty()){
        int nod = q.front();
        q.pop();

        for(auto it : v[nod]){
            if(viz[it])continue;
            viz[it] = 1;
            d[it] = d[nod] + 1;
            q.push(it);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(!viz[i])return -1;
        ans += d[i];
    }

    return ans;

}

void solve(){

    cin >> n;

    for(int i = 1, k; i <= n; i++){
        cin >> k;
        for(int j = 1, x; j <= k; j++){
            cin >> x;
            v[x].push_back(i);
        }
    }

    int ans = INF64;
    for(int i = 1; i <= n; i++){
        int x = bfs(i);
        if(x != -1)ans = min(ans, x);
    }

    if(ans == INF64){
        cout << "-1" << '\n';
        return;
    }

    cout << ans << '\n';
}



int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);

    //cout << setprecision(6) << fixed;

    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 768 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 7 ms 896 KB Output is correct
13 Correct 4 ms 896 KB Output is correct
14 Correct 149 ms 1016 KB Output is correct
15 Correct 27 ms 1024 KB Output is correct
16 Correct 600 ms 1144 KB Output is correct
17 Correct 756 ms 1116 KB Output is correct
18 Correct 784 ms 1144 KB Output is correct