oj.uz

Submission #574839

# Submission time Handle Problem Language Result Execution time Memory
574839 2022-06-09T12:30:58 Z talant117408 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 920 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;
}

ll dfs(int v, int p, vector <vector <int>> &graph, ll &sum) {
    ll total = 1;
    for (auto to : graph[v]) {
        if (to == p) continue;
        total += dfs(to, v, graph, sum);
    }
    sum += total;
    return total;
}

ll bfs(int v, int n, vector <vector <int>> &graph) {
    vector <vector <int>> hierarchy(n+1);
    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 2e9;
    }
    ll sum = 0;
    dfs(v, v, hierarchy, sum);
    return sum;
}

void solve() {
    int n;
    cin >> n;
    vector <vector <int>> graph(n+1);
    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, graph));
    }
    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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 2 ms 324 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 7 ms 344 KB Output is correct
13 Correct 5 ms 336 KB Output is correct
14 Correct 789 ms 912 KB Output is correct
15 Correct 58 ms 840 KB Output is correct
16 Execution timed out 1580 ms 920 KB Time limit exceeded
17 Halted 0 ms 0 KB -