Submission #1164124

#TimeUsernameProblemLanguageResultExecution timeMemory
1164124canhnam357Bosses (BOI16_bosses)C++20
100 / 100
385 ms736 KiB
// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
    f = (f > s ? f : s);
}
void ckmin(long long& f, long long s)
{
    f = (f < s ? f : s);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; i++)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int p;
            cin >> p;
            adj[--p].push_back(i);
            //cout << p << ' ' << i << '\n';
        }
    }
    long long ans = LLONG_MAX;
    for (int i = 0; i < n; i++)
    {
        vector<int> vis(n, -1);
        vis[i] = 0;
        long long cur = n;
        queue<int> q;
        q.push(i);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int v : adj[u])
            {
                if (vis[v] == -1)
                {
                    vis[v] = vis[u] + 1;
                    cur += vis[v];
                    q.push(v);
                }
            }
        }
        if (count(all(vis), -1) == 0) ckmin(ans, cur);
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...