Submission #764325

#	Time	Username	Problem	Language	Result	Execution time	Memory
764325		Ellinor	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	212 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;

int N,k;
vector<vector<int>> graph;
vector<bool> visited;
int a;

queue<pair<int,int>> q; //node, level


void bfs_calc(int node, int level) //bfs !
{
    a+=level;
    rep(i,0,graph[node].size()){
        if (!visited[graph[node][i]]) {
            q.push({graph[node][i],level+1});
            visited[graph[node][i]]=true;
        }
    }
}


int32_t main()
{
    cin>>N;
    graph.assign(N,{});
    //int root=-1;
    rep(i,0,N){
        cin>>k;
        rep(j,0,k){
            cin>>a;
            a--;
            //boss to employee
            graph[a].push_back(i);
        }
        //if(k==0)root=i;
    }

    int ans=1e6; //hm !
    // ki = 0 ?? !
    //if(root==-1){
    rep(i,0,N){
        visited.assign(N,false);
        //check all visited
        a=0;
        q.push({i,1});
        visited[i]=true;
        while(!q.empty()){
            auto x=q.front();
            q.pop();
            bfs_calc(x.first,x.second);
        }
        ans=min(ans,a);
    }
    // }
    // else{
    //     ans = dfs_calc(root);
    // }

    cout << ans;
}

Compilation message (stderr)

bosses.cpp: In function 'void bfs_calc(int, int)':
bosses.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int i = (a); i < (b); i++)
      |                                       ^
bosses.cpp:18:5: note: in expansion of macro 'rep'
   18 |     rep(i,0,graph[node].size()){
      |     ^~~

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