Submission #1097627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097627		Noname_1900	Bosses (BOI16_bosses)	C++17	67 / 100	171 ms	960 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 5000;
//set<int> chefsPossibles[NMAX];
vector<int> filsPossible[NMAX];
vector<int> fils[NMAX];
int dejaPris[NMAX];
#define INFINI 1000000
int sommeTotal;
int nbVu;
int parcourir(int noeud, int iDejaVu)
{
    /*
    if(dejaPris[noeud] != iDejaVu)  
    {
        sommeTotal += INFINI;
        return INFINI;
    }
    /**/
    nbVu++;
    int somme = 1;
    for(int pro : fils[noeud])
    {
        somme += parcourir(pro, iDejaVu);
    }
    sommeTotal += somme;
    return somme;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int nbEmploye;
    cin >> nbEmploye;
    for(int i = 0; i < nbEmploye; i++)
    {
        int nbChefs;
        cin >> nbChefs;
        for(int v = 0; v < nbChefs; v++)
        {
            int c;
            cin >> c;
            --c;
            //chefsPossibles[i].insert(c);
            filsPossible[c].push_back(i);
        }
    }
    /*
    for(int i = 0; i < nbEmploye; i++)
    {
        cout << i+1 << " : ";
        for(int v : filsPossible[i])    cout << v+1 << " ";
        cout << endl;
    }
    /**/
    int meill = INFINI;
    for(int PremBoss = 0; PremBoss < nbEmploye; PremBoss++)
    {
        vector<int> caseMAint;
        vector<int> proCase;
        proCase.push_back(PremBoss);
        dejaPris[PremBoss] = PremBoss+1;
    
        while(proCase.size())
        {
            caseMAint = proCase;
            proCase.clear();
            for(int noeud : caseMAint)
            {
                fils[noeud].clear();
                for(int pro : filsPossible[noeud])
                {
                    if(dejaPris[pro] == PremBoss+1) continue;
                    dejaPris[pro] = PremBoss+1;
                    proCase.push_back(pro);
                    fils[noeud].push_back(pro);
                }
            }
        }
        sommeTotal = 0;
        nbVu = 0;
        parcourir(PremBoss, PremBoss+1);
      //  cout << sommeTotal << " " << nbVu << endl;
        if(nbVu == nbEmploye)
            meill = min(meill, sommeTotal);
    }
    cout << meill;
}

Compilation message (stderr)

bosses.cpp:19:5: warning: "/*" within comment [-Wcomment]
   19 |     /**/
      |      
bosses.cpp:55:5: warning: "/*" within comment [-Wcomment]
   55 |     /**/
      |

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