Submission #699036

#	Time	Username	Problem	Language	Result	Execution time	Memory
699036		Richem	Bosses (BOI16_bosses)	C++14	100 / 100	867 ms	692 KiB

bosses

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

const int MAX_SOMMET = 5042, INF = 1e9;

int nbSommet;
vector<int> adj[MAX_SOMMET];

void input() {
    cin >> nbSommet;

    for(int sommet = 0; sommet < nbSommet; sommet++) {
        int nbVoisin;
        cin >> nbVoisin;

        for(int iVoisin = 0; iVoisin < nbVoisin; iVoisin++) {
            int idVoisin;
            cin >> idVoisin;

            adj[idVoisin-1].push_back(sommet);
        }
    }
}

bool vu[MAX_SOMMET];
int preced[MAX_SOMMET];
int rep[MAX_SOMMET] = {0};


int bfs(int depart) {
    for(int sommet = 0; sommet < nbSommet; sommet++) {
        vu[sommet] = rep[sommet] = 0;
    }

    queue<int> q;
    stack<int> ordre;

    q.push(depart);
    vu[depart] = 1;

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        ordre.push(cur);
        
        for(auto voisin : adj[cur]) {
            if(!vu[voisin]) {
                vu[voisin] = 1;
                preced[voisin] = cur;
                q.push(voisin);
            }
        }
    }

    if(ordre.size() != nbSommet) {
        return INF;
    }

    int total = 0;

    while(!ordre.empty()) {
        int cur = ordre.top();
        ordre.pop();

        rep[cur]++;
        if(cur != depart) {
            rep[preced[cur]] += rep[cur];
        }

        total += rep[cur];
    }

    return total;
}

int main() {
    input();

    int valMin = INF;

    for(int sommet = 0; sommet < nbSommet; sommet++) {
        valMin = min(valMin, bfs(sommet));
    }

    cout << valMin;
}

Compilation message (stderr)

bosses.cpp: In function 'int bfs(int)':
bosses.cpp:35:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   35 |         vu[sommet] = rep[sommet] = 0;
      |                      ~~~~~~~~~~~~^~~
bosses.cpp:58:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     if(ordre.size() != nbSommet) {
      |        ~~~~~~~~~~~~~^~~~~~~~~~~

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