oj.uz

Submission #362402

# Submission time Handle Problem Language Result Execution time Memory
362402 2021-02-03T05:49:00 Z gratus907 Bosses (BOI16_bosses) C++17
100 / 100
 691 ms 840 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

int n;
vector <int> G[5050];
int vst[5050];
int32_t main()
{
    usecppio
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int k; cin >> k;
        for (int j = 0; j < k; j++)
        {
            int p; cin >> p;
            G[p].push_back(i);
        }
    }
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++)
    {
        memset(vst, 0x7f, sizeof(vst));
        int cnt = 0;
        queue <int> q;
        q.push(i);
        cnt++;
        vst[i] = 1;
        while (!q.empty())
        {
            int t = q.front();
            q.pop();
            for (int nxt : G[t])
            {
                if (vst[nxt] > 10000)
                {
                    vst[nxt] = vst[t] + 1;
                    q.push(nxt);
                    cnt++;
                }
            }
        }
        if (cnt == n)
        {
            int sal = 0;
            for (int j = 1; j <= n; j++)
                sal += vst[j];
            ans = min(sal, ans);
        }
    }
    cout << ans << '\n';
}

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 512 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 512 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 512 KB Output is correct
11 Correct 1 ms 512 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 512 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 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 5 ms 620 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 115 ms 620 KB Output is correct
15 Correct 6 ms 620 KB Output is correct
16 Correct 570 ms 748 KB Output is correct
17 Correct 690 ms 840 KB Output is correct
18 Correct 691 ms 748 KB Output is correct