Submission #704733

#	Time	Username	Problem	Language	Result	Execution time	Memory
704733		speedyArda	Bosses (BOI16_bosses)	C++14	100 / 100	1310 ms	980 KiB

bosses

#include "bits/stdc++.h"

using namespace std;
const int MAXN = 5005;
vector< vector<int> > adj(MAXN), rev(MAXN);
int main() 
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int amount;
        cin >> amount;
        while(amount--)
        {
            int f;
            cin >> f;
            adj[i].push_back(f);
            rev[f].push_back(i);
        }
    }
    queue<int> q;
    long long res = 1e18;
    for(int i = 1; i <= n; i++)
    {
        vector<bool> visited(n+5);
        vector<int> indeg(n+5);
        vector<long long> ans(n+5);
        vector<int> par(n+5, 1e9);
        visited[i] = true;
        par[i] = -1;
        queue<int> q;
        q.push(i);
        while(!q.empty())
        {
            int v = q.front();
            q.pop();
            for(int e : rev[v])
            {
                if(visited[e])
                    continue;
                visited[e] = true;
                par[e] = v;
                indeg[v]++;
                q.push(e);
            }
        }
        for(int idx = 1; idx <= n; idx++)
        {
            if(indeg[idx] == 0)
                q.push(idx);
        }
        long long temp = 0;
        while(!q.empty())
        {
            int v = q.front();
            q.pop();
            ans[v]++;
            temp += ans[v];
            if(par[v] != -1 && par[v] != 1e9)
            {
                indeg[par[v]]--;
                ans[par[v]] += ans[v];
                if(indeg[par[v]] == 0)
                    q.push(par[v]);
            }

        }

        for(int i = 1; i <= n; i++)
        {
            if(par[i] == 1e9) // There is an element which isn't in the hierarchy
                temp = 1e18; 
        }

        res = min(res, temp);
    }

    cout << res << "\n";
}

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