Submission #1258975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258975		motion	Bosses (BOI16_bosses)	C++20	67 / 100	1594 ms	1208 KiB

bosses

#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;


}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33