Submission #208544

#	Time	Username	Problem	Language	Result	Execution time	Memory
208544		jzh	Bosses (BOI16_bosses)	C++14	67 / 100	1591 ms	760 KiB

bosses

#include <bits/stdc++.h>
#pragma O3
using namespace std;
typedef long long ll;
vector<ll>v[5010];
ll level[5010];
bool vis[5010];
ll sum;
ll dfs(ll node){
    //if (vis[node])return 0;
    vis[node]=1;
    ll ret=0;
    for (ll i=0;i<v[node].size();i++){
        if (level[v[node][i]]==level[node]+1&&!vis[v[node][i]]){
            ret+=dfs(v[node][i]);
        }
    }
    ret++;
    sum+=ret;
    //cout<<node<<' '<<ret<<'\n';
    return ret;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,i,x,y,k,ans=INT_MAX,i1,w,cnt;
    cin>>n;
    
    for (i=1;i<=n;i++){
        cin>>k;
        while (k--){
            cin>>x;
            v[x].push_back(i);
        }
    }
    queue<pair<ll,ll> >q;
    for (i=1;i<=n;i++){
        q.push({1,i});
        for (i1=1;i1<=n;i1++)level[i1]=-1,vis[i1]=0;
        level[i]=1;
        sum=0;
        cnt=0;
        while (!q.empty()){
            x=q.front().second;
            w=q.front().first;
            q.pop();
            cnt++;
            for (i1=0;i1<v[x].size();i1++){
                if (level[v[x][i1]]==-1){
                    level[v[x][i1]]=w+1;
                    q.push({w+1,v[x][i1]});
                    //cout<<x<<'.'<<v[x][i1]<<'\n';
                }
            }
        }
        if (cnt<n){
            continue;
        }
        dfs(i);
        ans=min(ans,sum);
        //cout<<i<<'\n';
        //cout<<sum<<'\n';
    }
    cout<<ans<<'\n';
}

Compilation message (stderr)

bosses.cpp:2:0: warning: ignoring #pragma O3  [-Wunknown-pragmas]
 #pragma O3
 
bosses.cpp: In function 'll dfs(ll)':
bosses.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i=0;i<v[node].size();i++){
                 ~^~~~~~~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:48:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i1=0;i1<v[x].size();i1++){
                       ~~^~~~~~~~~~~~
bosses.cpp:26:14: warning: unused variable 'y' [-Wunused-variable]
     ll n,i,x,y,k,ans=INT_MAX,i1,w,cnt;
              ^

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