oj.uz

Submission #39841

# Submission time Handle Problem Language Result Execution time Memory
39841 2018-01-20T21:12:39 Z MladenP Bosses (BOI16_bosses) C++14
100 / 100
 683 ms 2312 KB 
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define mid (l+r)/2
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 5010
vector<int> adj[MAXN];
lld dist[MAXN], n;
bool pos[MAXN];
queue<int> q;
lld BFS(int st) {
    for(int i = 1; i <= n; i++) pos[i] = 0;
    q.push(st);
    pos[st] = true; dist[st] = 1;
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for(auto x : adj[v]) {
            if(!pos[x]) {
                dist[x] = dist[v] + 1; pos[x] = true;
                q.push(x);
            }
        }
    }
    lld rez = 0;
    for(int i = 1; i <= n; i++) {
        if(!pos[i]) return LINF;
        rez += dist[i];
    }
    return rez;
}

int main() {
    //ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        for(int j = 1; j <= k; j++) {
            int x; cin >> x;
            adj[x].pb(i);
        }
    }
    lld rez = LINF;
    for(int i = 1; i <= n; i++) {
        rez = min(rez, BFS(i));
    }
    cout << rez;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2180 KB Output is correct
2 Correct 0 ms 2180 KB Output is correct
3 Correct 0 ms 2180 KB Output is correct
4 Correct 0 ms 2180 KB Output is correct
5 Correct 0 ms 2180 KB Output is correct
6 Correct 0 ms 2180 KB Output is correct
7 Correct 0 ms 2180 KB Output is correct
8 Correct 0 ms 2180 KB Output is correct
9 Correct 0 ms 2180 KB Output is correct
10 Correct 0 ms 2180 KB Output is correct
11 Correct 0 ms 2180 KB Output is correct
12 Correct 10 ms 2312 KB Output is correct
13 Correct 5 ms 2312 KB Output is correct
14 Correct 139 ms 2312 KB Output is correct
15 Correct 15 ms 2312 KB Output is correct
16 Correct 619 ms 2312 KB Output is correct
17 Correct 658 ms 2312 KB Output is correct
18 Correct 683 ms 2312 KB Output is correct