oj.uz

Submission #422468

# Submission time Handle Problem Language Result Execution time Memory
422468 2021-06-10T07:07:02 Z ak2006 Bosses (BOI16_bosses) C++14
100 / 100
 757 ms 668 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int n;
    cin>>n;
    vvi adj(n + 1);
    for (int i = 1;i<=n;i++){
        int x;
        cin>>x;
        while (x--){
            int y;
            cin>>y;
            adj[y].pb(i);
        }
    }
    ll ans = inf;
    for (int i = 1;i<=n;i++){
        //root the tree at i and use BFS because that creates the min salaries
        //instead of finding each nodes' salary find the contribution of that node to its 
        //ancestors
        //realise that the contribution is just that nodes depth
        vl dep(n + 1);
        dep[i] = 1;
        queue<int>q;
        q.push(i);
        ll now = 0;
        int cnt = 0;
        while (!q.empty()){
            int cur = q.front();
            q.pop();
            cnt++;
            now += dep[cur];
            for (int x:adj[cur]){
                if (dep[x] == 0){
                    dep[x] = dep[cur] + 1;
                    q.push(x);
                }
            }
        }
        if (cnt == n)ans = min(ans,now);
    }
    cout<<ans;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 5 ms 332 KB Output is correct
13 Correct 4 ms 332 KB Output is correct
14 Correct 131 ms 568 KB Output is correct
15 Correct 10 ms 588 KB Output is correct
16 Correct 608 ms 648 KB Output is correct
17 Correct 757 ms 668 KB Output is correct
18 Correct 727 ms 588 KB Output is correct