Submission #1280267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280267		hanguyendanghuy	Bosses (BOI16_bosses)	C++20	100 / 100	746 ms	1128 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
constexpr ll MAXN=3e5+5,MAXV=3e5,MOD=1e9+7,INF=1e18;
ll n,m,i,j,p,k,ans=INF,dem,st,en,dist[MAXN],vis[MAXN];
vector<ll> adj[MAXN],canh[MAXN];
ll dfs(ll st,ll pre){
    ll ans=0;
    for(ll x:canh[st]){
        ans+=dfs(x,st);
        dist[st]+=dist[x];
    }
    return ans+dist[st];
}
void solve(ll st){
    queue<ll> q;
    q.push(st);
    ll cnt=1;
    vis[st]=1;
    while(q.size()){
        ll k=q.front();q.pop();
        for(ll x:adj[k]){
            if(!vis[x]){
                cnt++;
                vis[x]=1;
                canh[k].pb(x);
                q.push(x);
            }
        }
    }
    if(cnt<n) return;
    ans=min(ans,dfs(st,st));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>m;
        for(j=1;j<=m;j++){
            cin>>k;
            adj[k].pb(i);
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++) dist[j]=1,vis[j]=0,canh[j].clear();
        solve(i);
    }
    cout<<ans;
}

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