oj.uz

Submission #699036

# Submission time Handle Problem Language Result Execution time Memory
699036 2023-02-15T12:03:58 Z Richem Bosses (BOI16_bosses) C++14
100 / 100
 867 ms 692 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 432 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 4 ms 440 KB Output is correct
14 Correct 129 ms 576 KB Output is correct
15 Correct 7 ms 596 KB Output is correct
16 Correct 523 ms 596 KB Output is correct
17 Correct 867 ms 684 KB Output is correct
18 Correct 855 ms 692 KB Output is correct