Submission #236299

#	Time	Username	Problem	Language	Result	Execution time	Memory
236299		mehrdad_sohrabi	Bosses (BOI16_bosses)	C++14	100 / 100	1481 ms	1272 KiB

bosses

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=5e3+10;
vector <int> g[N];
ll par[N];
bool vis[N];
vector <int> y[N];
void bfs(ll x){
    memset(par,0,sizeof par);
    queue <int> q;
    q.push(x);
    memset(vis,0,sizeof vis);
    vis[x]=1;
    while(q.size()){
        ll v=q.front();
        q.pop();
        for (auto u : g[v]){
            if (!vis[u]){
                vis[u]=1;
                par[u]=v;
                y[v].pb(u);
                q.push(u);
            }
        }
    }
}
ll dp[N];
ll dfs(ll v,ll p){
    for (auto u : y[v]){
        if (u==p) continue;
        dfs(u,v);
        dp[v]+=dp[u];
    }
    dp[v]+=1;
}
int32_t main(){
    ll n;
    cin >> n;
    for (int i=1;i<=n;i++){
        ll k;
        cin >> k;
        for (int j=0;j<k;j++){
            ll x;
            cin >> x;
            g[x].pb(i);
        }
    }
    ll ans=(ll)1e15;
    for (int i=1;i<=n;i++){
        for (int j=0;j<N;j++) y[j].clear(),dp[j]=0;
        bfs(i);
        dfs(i,i);
        for (int j=1;j<=n;j++) if (dp[j]==0) dp[i]=(ll)1e15;
        ll cnt=0;
        for (int j=1;j<=n;j++) cnt+=dp[j];
        ans=min(ans,cnt);
    }
    cout << ans << endl;
}

Compilation message (stderr)

bosses.cpp: In function 'll dfs(ll, ll)':
bosses.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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