Submission #1072860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072860		Jarif_Rahman	Bosses (BOI16_bosses)	C++17	100 / 100	390 ms	764 KiB

bosses

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<int> bfs(const vector<vector<int>> &graph, int source){
    int n = graph.size();
    vector<int> dis(n, -1);
    queue<int> Q;
    dis[source] = 0;
    Q.push(source);
    
    while(!Q.empty()){
        int nd = Q.front();
        Q.pop();
        for(int x: graph[nd]) if(dis[x] == -1){
            dis[x] = dis[nd]+1;
            Q.push(x);
        }
    }

    return dis;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<vector<int>> graph(n);
    for(int i = 0; i < n; i++){
        int k; cin >> k;
        while(k--){
            int p; cin >> p; p--;
            graph[p].push_back(i);
        }
    }

    int ans = 1e9;
    for(int i = 0; i < n; i++){
        auto dis = bfs(graph, i);
        int cur = n;
        for(int x: dis){
            if(x == -1){
                cur = 1e9;
                break;
            }
            cur+=x;
        }
        ans = min(ans, cur);
    }

    cout << ans << "\n";
}

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