oj.uz

Submission #986474

# Submission time Handle Problem Language Result Execution time Memory
986474 2024-05-20T15:42:38 Z ShaShi Bosses (BOI16_bosses) C++17
100 / 100
 436 ms 25484 KB 
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define kill(x) cout << x << endl, exit(0);
#define endl "\n"

 
using namespace std;
typedef long long ll;
typedef long double ld;
 

const int MAXN = (int)1e6 + 7;
const int MOD = 998244853;
const ll INF = (ll)1e18 + 7;


int n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M;
int arr[MAXN], h[MAXN];
bool seen[MAXN];
vector<int> adj[MAXN];
queue<int> Q;


void BFS(int v) {
    fill(seen, seen+n+1, 0);

    tmp = 0; Q.push(v); h[v] = seen[v] = 1;

    while (Q.size()) {
        v = Q.front(); Q.pop();

        // cout << "@" << v << " " << h[v] << endl;

        tmp += h[v];

        for (int u:adj[v]) {
            if (!seen[u]) {
                seen[u] = 1; h[u] = h[v]+1;

                Q.push(u);
            }
        }
    }

    for (int i=1; i<=n; i++) if (!seen[i]) return;

    ans = min(ans, tmp);
}


int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i=1; i<=n; i++) {
        cin >> k;

        for (int j=1; j<=k; j++) {
            cin >> u;

            adj[u].pb(i);
        }
    }

    ans = INF;

    
    for (int i=1; i<=n; i++) BFS(i);

    cout << ans << endl;

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25176 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 5 ms 25180 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25260 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25176 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 5 ms 25180 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25260 KB Output is correct
6 Correct 6 ms 25180 KB Output is correct
7 Correct 6 ms 25176 KB Output is correct
8 Correct 6 ms 25180 KB Output is correct
9 Correct 5 ms 25180 KB Output is correct
10 Correct 7 ms 25176 KB Output is correct
11 Correct 6 ms 25252 KB Output is correct
12 Correct 8 ms 25180 KB Output is correct
13 Correct 8 ms 25436 KB Output is correct
14 Correct 85 ms 25180 KB Output is correct
15 Correct 9 ms 25180 KB Output is correct
16 Correct 428 ms 25480 KB Output is correct
17 Correct 412 ms 25436 KB Output is correct
18 Correct 436 ms 25484 KB Output is correct