Submission #1315174

#TimeUsernameProblemLanguageResultExecution timeMemory
1315174BigBadBullyBosses (BOI16_bosses)C++20
100 / 100
687 ms948 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define tri array<int,3>
const int inf = 1e18;
const int mod = 1e9+7;
const int mxn = 1e6 + 1;
int exp(int x, int n)
{
    int res = 1;
    for (; n > 0; res = (n % 2 ? res * x % mod : res), x = x * x % mod, n /= 2)
        ;
    return res;
}

int inv(int x)
{
    return exp(x, mod - 2);
}

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> graph(n);
    
    for(int i = 0; i < n; i++)
    {
        int sz;
        cin >> sz;
        while(sz--)
        {
            int a;
            cin >> a;
            graph[--a].push_back(i);
        }
    }
    int mini = inf;
    for(int rt = 0;rt < n; rt++)
    {
        queue<pii> bfs;
        vector<vector<int>> tree(n);
        vector<int> vis(n,0);
        bfs.push({rt,rt});
        vector<int> dp(n,inf);
        dp[rt] = 1;
        while(bfs.size())
        {
            pii cur =bfs.front();
            bfs.pop();
            if(vis[cur.ff])continue;
            vis[cur.ff] = 1;
            for(int a : graph[cur.ff])
                bfs.push({a,cur.ff}),dp[a]=min(dp[a],dp[cur.ff]+1);
        }
        int sum = 0;
        for(int i = 0; i < n; i++)
        {
            if(sum>inf)
                break;
            sum+=dp[i];
        }
        mini =min(mini,sum);
    }
    cout << mini << '\n';
}   
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	srand(time(0));
    int t = 1;
    //cin >>t;
    while (t--)
        solve();
	
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...