Submission #1304565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304565		chybazuzia	Bosses (BOI16_bosses)	C++20	100 / 100	750 ms	1184 KiB

bosses

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

#define ll long long

const int N = 5e3+5;
vector <int> graf[ N ], tree[ N ];
bool vis[ N ], odw[ N ];
ll ile[ N ];
queue <int> kol;

void dfs( int x ){
    odw[ x ]=1;
    for( int i : tree[x] ){
        if( !odw[ i ] ){
            dfs( i );
            ile[ x ] += ile[ i ];
        }
    }
    ile[ x ]++;
    return;
}

ll wyz( int ilewar ){
    ll wyn = 0;
    for( int i = 0 ; i <= ilewar ; ++i ){
        odw[i]=0;
        vis[i]=0;
        wyn += ile[i];
        ile[i]=0;
        tree[i].clear();
    }
    while( !kol.empty() )
        kol.pop();
    return wyn;
}

bool ustal( int x, int ilewar ){
    vis[ x ]=1;
    int od = 0;
    kol.push( x );
    while( !kol.empty() ){
        int u = kol.front() ;
        od++ ;
        kol.pop();
        for( int i : graf[ u ] )
            if( !vis[i] ){
                tree[u].push_back(i);
                vis[i]=1;
                kol.push(i);
            }
    }
    if( ilewar <= od )
        return 1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll ilewar, ilepol, pol1, odp=1e18;
    cin >> ilewar ;
    for( int i = 1 ; i <= ilewar ; ++i ){
        cin >> ilepol ;
        for( int j=1; j<=ilepol; ++j ){
            cin >> pol1;
            graf[pol1].push_back(i);
        }
    }
    for( int i=1; i <= ilewar ; ++i ){
        wyz(ilewar);
        if( !ustal(i, ilewar) )
            continue;
        dfs(i);
        odp = min( odp, wyz(ilewar) );
    }
    cout << odp << '\n';

    return 0;
}

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