Submission #208847

#	Time	Username	Problem	Language	Result	Execution time	Memory
208847		jzh	Bosses (BOI16_bosses)	C++14	67 / 100	1592 ms	888 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,sum=0;
    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],par[5010],val[5010];
    bool vis[5010];
    priority_queue<pair<ll,ll> >pq;
    for (i=1;i<=n;i++){
        q.push({1,i});
        for (i1=1;i1<=n;i1++)level[i1]=-1,vis[i1]=0,val[i1]=-1,par[i1]=-1;
        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]});
                    par[v[x][i1]]=x;
                    vis[x]=1;
                    //cout<<x<<'.'<<v[x][i1]<<'\n';
                }
            }
        }
        if (cnt<n){
            continue;
        }
        for (i1=1;i1<=n;i1++){
            if (!vis[i1]){
                pq.push({level[i1],i1});
                val[i1]=1;
                //cout<<i1<<"..."<<'\n';
                vis[i1]=1;
            }
            else {
                vis[i1]=0;
            }
            
        }
        
        while (!pq.empty()){
            x=pq.top().second;
            w=1;
            pq.pop();
            for (i1=0;i1<v[x].size();i1++){
                if (par[v[x][i1]]==x){
                    w+=val[v[x][i1]];
                }
            }
            val[x]=w;
            sum+=w;
            //cout<<x<<' '<<w<<' '<<val[x]<<'\n';
            if (par[x]!=-1&&vis[par[x]]==0){
                pq.push({level[par[x]],par[x]});
                vis[par[x]]=1;
            }
        }
        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:34:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i1=0;i1<v[x].size();i1++){
                       ~~^~~~~~~~~~~~
bosses.cpp:64:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (i1=0;i1<v[x].size();i1++){
                       ~~^~~~~~~~~~~~
bosses.cpp:8:14: warning: unused variable 'y' [-Wunused-variable]
     ll n,i,x,y,k,ans=INT_MAX,i1,w,cnt,sum=0;
              ^

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