Submission #1016780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016780		inesfi	Bosses (BOI16_bosses)	C++14	100 / 100	1105 ms	1128 KiB

bosses

#include<bits/stdc++.h>
using namespace std;

const int TAILLEMAXI=5002;
int nbpers,nbpos,val,taille,ec,pere,rep,total,pb;
vector<int> enfantspos[TAILLEMAXI];
vector<int> fils[TAILLEMAXI];
int dejapris[TAILLEMAXI];
deque<pair<int,int>> encours;

int trouver(int a){
    int somme;
    somme=0;
    for (int i=0;i<(int)fils[a].size();i++){
        somme+=trouver(fils[a][i]);
    }
    //cout<<a<<" "<<somme<<endl;
    somme++;
    total+=somme;
    return somme;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nbpers;
    for (int i=1;i<=nbpers;i++){
        cin>>nbpos;
        for (int ipos=0;ipos<nbpos;ipos++){
            cin>>val;
            enfantspos[val].push_back(i);
        }
    }
    rep=TAILLEMAXI*TAILLEMAXI;
    for (int ideb=1;ideb<=nbpers;ideb++){
        for (int i=1;i<=nbpers;i++){
            fils[i].clear();
        }
        encours.push_back({ideb,0});
        while (encours.size()!=0){
            taille=encours.size();
            for (int i=0;i<taille;i++){
                ec=encours.front().first;
                pere=encours.front().second;
                encours.pop_front();
                if (dejapris[ec]!=ideb){
                    fils[pere].push_back(ec);
                    dejapris[ec]=ideb;
                    for (int ipos=0;ipos<(int)enfantspos[ec].size();ipos++){
                        if (dejapris[enfantspos[ec][ipos]]!=ideb){
                            encours.push_back({enfantspos[ec][ipos],ec});
                        }
                    }
                }
            }
        }
        pb=0;
        for (int i=1;i<=nbpers;i++){
            if (dejapris[i]!=ideb){
                pb=1;
            }
        }
        if (pb==0){
            //cout<<ideb<<endl;
            total=0;
            val=trouver(ideb);
            rep=min(rep,total);
            //cout<<total<<endl;
        }
    }
    cout<<rep<<endl;
    return 0;
}

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