Submission #46794

#	Time	Username	Problem	Language	Result	Execution time	Memory
46794		oTTo_22	Bosses (BOI16_bosses)	C++17	100 / 100	1138 ms	1332 KiB

bosses

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int INF=1e9;

vector < vector < int > > g;

int main() {

    ios_base::sync_with_stdio(false);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int n;
    cin >> n;

    g.resize(n+1);

    for (int i=1; i<=n; i++) {
        int k;
        cin >> k;
        while (k--) {
            int a;
            cin >> a;
            g[a].push_back(i);
        }
    }

    /*for (int i=1; i<=n; i++) {
        for (int j=0; j<g[i].size(); j++)
            cout << g[i][j] << " ";
        cout << "\n";
    }*/

    int ans=INF;

    for (int i=1; i<=n; i++) {

        stack < pair < int,int > > st;
        queue < pair < int,int > > q;
        vector < bool > used(n+1,0);
        vector < int > vc(n+1,0);

        q.push({i,-1});
        used[i]=1;

        while (!q.empty()) {
            pair < int,int > v=q.front();
            //cout << i << "->" << v.fi << " " << v.se << "\n";
            st.push(v);
            q.pop();
            for (int i=0; i<g[v.fi].size(); i++) {
                int to=g[v.fi][i];
                if (!used[to]) {
                    used[to]=1;
                    q.push({to,v.fi});
                }
            }
        }

        while (!st.empty()) {
            pair < int,int > v=st.top();
            st.pop();
            if (!st.empty()) {
                vc[v.fi]++;
                vc[v.se]+=vc[v.fi];
            }
            else
                vc[v.fi]++;
        }

        int cnt=0;
        bool ind=0;

        for (int i=1; i<=n; i++) {
            if (!vc[i]) {
                ind=1;
                break;
            }
            cnt+=vc[i];
        }

        if (!ind)
            ans=min(ans,cnt);

    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:55:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i=0; i<g[v.fi].size(); i++) {
                           ~^~~~~~~~~~~~~~~

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