oj.uz

Submission #163684

# Submission time Handle Problem Language Result Execution time Memory
163684 2019-11-14T14:52:50 Z alexandra_udristoiu Bosses (BOI16_bosses) C++14
100 / 100
 897 ms 860 KB 
#include<iostream>
#include<vector>
#include<cstring>
#define DIM 5005
using namespace std;
int n, i, j, m, x, sum, sol;
int viz[DIM], niv[DIM], c[DIM];
vector<int> v[DIM];
void bfs(int srs){
   int nod, vecin, i, j, p, u;
   p = u = viz[srs] = 1;
   c[1] = srs;
   niv[srs] = 1;
   while(p <= u){
       nod = c[p];
       sum += niv[nod];
       p++;
       for(j = 0; j < v[nod].size(); j++){
            vecin = v[nod][j];
            if(viz[vecin] == 0){
                viz[vecin] = 1;
                niv[vecin] = 1 + niv[nod];
                c[++u] = vecin;
            }
       }
   }
   if(u != n){
        sum = 1000000000;
   }
}
int main(){
    cin>> n;
    for(i = 1; i <= n; i++){
        cin>> m;
        for(j = 1; j <= m; j++){
            cin>> x;
            v[x].push_back(i);
        }
    }
    sol = 1000000000;
    for(i = 1; i <= n; i++){
        memset(viz, 0, sizeof(viz) );
        sum = 0;
        bfs(i);
        sol = min(sol, sum);
    }
    cout<< sol;
}

Compilation message

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:18:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(j = 0; j < v[nod].size(); j++){
                   ~~^~~~~~~~~~~~~~~
bosses.cpp:10:20: warning: unused variable 'i' [-Wunused-variable]
    int nod, vecin, i, j, p, u;
                    ^

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 9 ms 504 KB Output is correct
13 Correct 8 ms 504 KB Output is correct
14 Correct 135 ms 680 KB Output is correct
15 Correct 9 ms 628 KB Output is correct
16 Correct 609 ms 760 KB Output is correct
17 Correct 897 ms 860 KB Output is correct
18 Correct 882 ms 780 KB Output is correct