Submission #79519

#	Time	Username	Problem	Language	Result	Execution time	Memory
79519		Vinhspm	Bosses (BOI16_bosses)	C++14	100 / 100	718 ms	996 KiB

bosses

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;

const int N = 5005;
const int oo = 1e9;

int n, ans = oo;
bool visit[N];
vector<int> vi[N];

void solve(int root)    {
    int sum = 0;
    memset(visit, false, sizeof visit);
    queue<ii> pq; pq.push(ii(root, 1));
    visit[root] = true;
    while(!pq.empty())  {
        ii cur = pq.front();
        pq.pop();
        sum += cur.se;
        for(int v: vi[cur.fi])  if(!visit[v]){
            visit[v] = true;
            pq.push(ii(v, cur.se + 1));
        }
    }
    for(int i = 1; i <= n; ++i) if(!visit[i]) return;
    ans = min(ans, sum);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int x; cin >> x;
        for(int j = 1; j <= x; ++j) {
            int u; cin >> u;
            vi[u].pb(i);
        }
    }
    for(int i = 1; i <= n; ++i) solve(i);
    cout << ans;
}

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