oj.uz

Submission #378073

# Submission time Handle Problem Language Result Execution time Memory
378073 2021-03-15T22:48:52 Z nextgenxing Bosses (BOI16_bosses) C++17
100 / 100
 1144 ms 876 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define f first
#define s second
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define F0Rd(i, x) FORd(i, 0, x)
#define ckif(a, b, c) ((c) ? (a) : (b))
const int MAX_N = 5001;
const ll MOD = 1000000007;
const ll INF = 1e18;

int n;
vector<int> adj[MAX_N];

int main(int argc, const char * argv[]){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    F0R(i, n){
        int a; cin >> a;
        F0R(j, a){
            int x; cin >> x; x--;
            adj[x].push_back(i);
        }
    }
    ll ans = INF;
    F0R(i, n){
        // i is the root of the tree
        // ans for this root is just the sum of the depths of all nodes
        // it is optimal to use the shortest path tree starting from i
        vector<ll> dist(n, -1);
        queue<pll> q; q.push({i, 1});
        while(!q.empty()){
            ll curr = q.front().f, cost = q.front().s; q.pop();
            if(~dist[curr]) continue;
            dist[curr] = cost;
            for(int child : adj[curr])
                q.push({child, cost+1});
        }
        ll tot = 0;
        bool ok = true;
        F0R(j, n) tot += dist[j], ok = ok && ~dist[j];
        if(ok) ans = min(ans, tot);
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 28 ms 772 KB Output is correct
13 Correct 21 ms 792 KB Output is correct
14 Correct 194 ms 620 KB Output is correct
15 Correct 39 ms 620 KB Output is correct
16 Correct 845 ms 876 KB Output is correct
17 Correct 1141 ms 876 KB Output is correct
18 Correct 1144 ms 876 KB Output is correct