oj.uz

Submission #946198

# Submission time Handle Problem Language Result Execution time Memory
946198 2024-03-14T12:03:36 Z veljko Bosses (BOI16_bosses) C++17
100 / 100
 429 ms 852 KB 
/*
        Baltic 16-Bosses
 
    Make the given input a directed graph, where if employee i accepts node j as boss, create an edge between j and i
    Then, do a BFS from each node and for each new node found, add to the answer (level of its dad + 1), so that we
won't need to do DFS anymore
 
*/
#include<bits/stdc++.h>
using namespace std;
int n, cost, ans = (1<<30);
vector<int>v[5002];
int viz[5002];
int s;
void bfs(int nod)
{
    memset(viz, 0, sizeof(viz));
    viz[nod] = 1;
    queue<int>q;
    q.push(nod);
    cost = 1;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        for(int j = 0; j < v[t].size(); ++j)
        {
            int vecin = v[t][j];
            if(!viz[vecin])
            {
                s++;
                viz[vecin] = viz[t] + 1;
                cost += viz[vecin];
                q.push(vecin);
            }
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        int k;
        cin >> k;
        for(int j = 1; j <= k; ++j)
        {
            int nr;
            cin >> nr;
            v[nr].push_back(i);
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        s = 0;
        cost = 0;
        bfs(i);
        if(s == n-1)
            ans = min(ans, cost);
    }
    cout << ans;
    return 0;
}

Compilation message

bosses.cpp: In function 'void bfs(int)':
bosses.cpp:26:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j = 0; j < v[t].size(); ++j)
      |                        ~~^~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 4 ms 604 KB Output is correct
14 Correct 70 ms 604 KB Output is correct
15 Correct 4 ms 604 KB Output is correct
16 Correct 429 ms 744 KB Output is correct
17 Correct 390 ms 852 KB Output is correct
18 Correct 381 ms 568 KB Output is correct