oj.uz

Submission #876523

# Submission time Handle Problem Language Result Execution time Memory
876523 2023-11-21T21:46:29 Z aykhn Bosses (BOI16_bosses) C++17
100 / 100
 445 ms 808 KB 
#include <bits/stdc++.h>
 
// author : aykhn
 
using namespace std;
typedef long long ll;
 
#define pb push_back
#define pf push_front
#define ins insert
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define bpc __builtin_popcountll
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define fi first
#define se second
#define int ll
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F

const int mxn = 5000 + 5;

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

int bfs(int a)
{
    queue<int> q;
    q.push(a);
    vector<int> dist(n + 1, inf);
    dist[a] = 1;
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        for (int v : adj[a])
        {
            if (dist[v] > dist[a] + 1)
            {
                dist[v] = dist[a] + 1;
                q.push(v);
            }
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) res += dist[i];
    return res;
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++)
        {
            int x;
            cin >> x;
            adj[x].pb(i);
        }
    }
    int res = inf;
    for (int i = 1; i <= n; i++) res = min(res, bfs(i));
    cout << res << '\n';
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 556 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 560 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 556 KB Output is correct
6 Correct 0 ms 500 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 560 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 588 KB Output is correct
14 Correct 98 ms 696 KB Output is correct
15 Correct 22 ms 604 KB Output is correct
16 Correct 433 ms 808 KB Output is correct
17 Correct 445 ms 792 KB Output is correct
18 Correct 408 ms 792 KB Output is correct