Submission #1187649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187649		njoop	Bosses (BOI16_bosses)	C++20	22 / 100	0 ms	584 KiB

bosses

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

int n, m, ans=1e18, s[5010];
vector<int> g[5010], li[5010];

int bfs(int no) {
    int c, cnt=0;
    queue<int> q;
    stack<int> st;
    for(int i=1; i<=n; i++) {
        s[i] = 1e18;
        li[i].clear();
    }
    q.push(no);
    s[no] = 1;
    st.push(no);
    while(q.size()) {
        int cn = q.front();
        q.pop();
        for(auto i: g[cn]) {
            if(s[i] != 1e18) continue;
            li[cn].push_back(i);
            q.push(i);
            s[i] = 1;
            st.push(i);
        }
    }
    while(st.size()) {
        int cn = st.top();
        st.pop();
        for(auto i: li[cn]) {
            s[cn] += s[i];
        }
    }
    for(int i=1; i<=n; i++) {
        cnt += s[i];
    }
    return cnt;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        int t, in;
        cin >> t;
        while(t--) {
            cin >> in;
            g[in].push_back(i);
        }
    }
    for(int i=1; i<=n; i++) {
        ans = min(ans, bfs(i));
    }
    cout << ans;
    return 0;
}

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