Submission #1166628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166628		Choco	Bosses (BOI16_bosses)	C++20	100 / 100	488 ms	2656 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
#define Study ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ff first 
#define ss second
#define ins insert
#define all(x) x.begin(),x.end()
#define fori(x,y,z) for(ll x=y;x<=z;x++)
const ll INF=1e18;
const ll sz=5e4+10;
const ll mod=1e9+7;
vector<vector<ll>>graph(sz);
vector<ll>check(sz,0),subt(sz,0);
ll bfs(ll t){
    check[t]=1;
    queue<ll>q;
    stack<pair<ll,ll>>parents;
    q.push(t);
    while(!q.empty()){
        ll node=q.front();
        q.pop();
        for(auto x: graph[node]){
            if(!check[x]){
                q.push(x);
                parents.push({x,node});
                check[x]=1;
            }
        }
    }
    ll cnt=0;
    while(!parents.empty()){
        ll node=parents.top().ff;
        ll par=parents.top().ss;
        subt[par]+=subt[node];
        cnt+=subt[node];
        parents.pop();
    }
    return subt[t]+cnt;
}
void work(){
    ll n;
    cin>>n;
    fori(i,1,n){
        ll k;
        cin>>k;
        fori(j,1,k){
            ll v;
            cin>>v;
            graph[v].pb(i);
        }
    }
    ll ans=INF;
    fori(i,1,n){
        subt.assign(n+10,1);
        check.assign(n+10,0);
        ll temp=bfs(i);
        bool okay=0;
        fori(i,1,n){
            if(!check[i])
            okay=1;
        }
        if(!okay)
        ans=min(ans,temp);
    }
    cout<<ans;
}
int main(){
    Study;
    ll t=1;
    //cin>>t;
    while(t--){
        work();
    }
}

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