Submission #208849

#	Time	Username	Problem	Language	Result	Execution time	Memory
208849		jzh	Bosses (BOI16_bosses)	C++14	67 / 100	1588 ms	1120 KiB

bosses

#include <bits/stdc++.h>
#pragma O3
using namespace std;
typedef long long ll;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,i,x,y,k,ans=INT_MAX,i1,w,cnt,maxlvl=0,i2;
    cin>>n;
    vector<ll>v[5010];
    for (i=1;i<=n;i++){
        cin>>k;
        while (k--){
            cin>>x;
            v[x].push_back(i);
        }
    }
    queue<pair<ll,ll> >q;
    
    ll level[5010],val[5010],par[5010];
    ll sum;
    for (i=1;i<=n;i++){
        vector<ll>lvls[5010];
        q.push({1,i});
        for (i1=1;i1<=n;i1++)level[i1]=-1,val[i1]=0,par[i1]=-1;
        level[i]=1;
        sum=0;
        cnt=0;
        while (!q.empty()){
            x=q.front().second;
            w=q.front().first;
            q.pop();
            cnt++;
            maxlvl=max(level[x],maxlvl);
            lvls[level[x]].push_back(x);
            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]});
                    par[v[x][i1]]=x;
                    //cout<<x<<'.'<<v[x][i1]<<'\n';
                }
            }
        }
        if (cnt<n){
            continue;
        }
        for (;maxlvl>=1;maxlvl--){
            for (i1=0;i1<lvls[maxlvl].size();i1++){
                x=lvls[maxlvl][i1];
                val[x]=1;
                for (i2=0;i2<v[x].size();i2++){
                    if (par[v[x][i2]]==x){
                        val[x]+=val[v[x][i2]];
                    }
                }
                sum+=val[x];
            }
        }
        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 'int main()':
bosses.cpp:36:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i1=0;i1<v[x].size();i1++){
                       ~~^~~~~~~~~~~~
bosses.cpp:49:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i1=0;i1<lvls[maxlvl].size();i1++){
                       ~~^~~~~~~~~~~~~~~~~~~~
bosses.cpp:52:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (i2=0;i2<v[x].size();i2++){
                           ~~^~~~~~~~~~~~
bosses.cpp:8:14: warning: unused variable 'y' [-Wunused-variable]
     ll n,i,x,y,k,ans=INT_MAX,i1,w,cnt,maxlvl=0,i2;
              ^

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