Submission #1258975

#TimeUsernameProblemLanguageResultExecution timeMemory
1258975motionBosses (BOI16_bosses)C++20
67 / 100
1594 ms1208 KiB
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> g,temp;
long long sum=0;
long long dfs(int v)
{
    long long cursum=1;
    for(auto x:temp[v])
    {
        cursum+=dfs(x);
    }
    sum+=cursum;
    return cursum;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    g=vector<vector<int>>(n);
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int curr;
            cin>>curr;
            curr--;
            g[curr].push_back(i);
        }
    }
    long long ans=1e15;
    for(int i=0;i<n;i++)
    {
        vector<bool> vis(n,0);
        temp=vector<vector<int>>(n);
        sum=0;
        int COUNT=0;
        queue<int> q;
        q.push(i);
        vis[i]=1;
        while(!q.empty())
        {
            auto v=q.front();
            COUNT++;
            q.pop();
            for(auto x:g[v])
            {
                if(vis[x]==1) continue;
                vis[x]=1;
                temp[v].push_back(x);
                q.push(x);
            }
        }
        if(COUNT<n) continue;
        dfs(i);
        ans=min(ans,sum);
    }
    cout<<ans;


}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...