Submission #699035

#TimeUsernameProblemLanguageResultExecution timeMemory
699035RichemBosses (BOI16_bosses)C++14
0 / 100
0 ms432 KiB
#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); while(!q.empty()) { int cur = q.front(); vu[cur] = 1; q.pop(); ordre.push(cur); for(auto voisin : adj[cur]) { if(!vu[voisin]) { 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:34:34: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   34 |         vu[sommet] = rep[sommet] = 0;
      |                      ~~~~~~~~~~~~^~~
bosses.cpp:56:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     if(ordre.size() != nbSommet) {
      |        ~~~~~~~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...