oj.uz

Submission #574851

# Submission time Handle Problem Language Result Execution time Memory
574851 2022-06-09T12:36:00 Z talant117408 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 956 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 5003;
vector <int> graph[N], hierarchy[N];
ll total;

ll dfs(int v, int p) {
    ll children_total = 1;
    for (auto to : hierarchy[v]) {
        if (to == p) continue;
        children_total += dfs(to, v);
    }
    total += children_total;
    return children_total;
}

ll bfs(int v, int n) {
    for (int i = 1; i <= n; i++) hierarchy[i].clear();
    total = 0;
    vector <int> dist(n+1, 2e9);
    dist[v] = 0;
    queue <int> K;
    K.push(v);
    while (!K.empty()) {
        auto u = K.front(); K.pop();
        for (auto to : graph[u]) {
            if (dist[to] > dist[u] + 1) {
                hierarchy[u].pb(to);
                hierarchy[to].pb(u);
                dist[to] = dist[u] + 1;
                K.push(to);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (dist[i] > n) return 9e18;
    }
    dfs(v, v);
    return total;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int x;
            cin >> x;
            graph[x].pb(i);
        }
    }
    
    ll ans = 9e18;
    for (int i = 1; i <= n; i++) {
        ans = min(ans, bfs(i, n));
    }
    cout << ans;
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 564 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 564 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 5 ms 700 KB Output is correct
13 Correct 4 ms 724 KB Output is correct
14 Correct 299 ms 916 KB Output is correct
15 Correct 42 ms 840 KB Output is correct
16 Correct 891 ms 956 KB Output is correct
17 Execution timed out 1571 ms 852 KB Time limit exceeded
18 Halted 0 ms 0 KB -