Submission #764348

#	Time	Username	Problem	Language	Result	Execution time	Memory
764348		Ellinor	Bosses (BOI16_bosses)	C++14	100 / 100	605 ms	620 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;
ll 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;
    }

    ll ans=1e17; //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);
            }
            bool b=true;
            while(true){
                rep(i,0,visited.size()){
                    if(!visited[i]){
                        b=false;
                        //assert(1==0);
                    }
                }
                break;
            }
            if(b) ans=min(ans,a);
        }
    }
    else{
        visited.assign(N,false);
        a=0;
        q.push({root,1});
        visited[root]=true;
        while(!q.empty()){
            auto x=q.front();
            q.pop();
            bfs_calc(x.first,x.second);
        }
        while(true){
            rep(i,0,visited.size()){
                if(!visited[i]){
                    assert(1==0);
                }
            }
            break;
        }
        ans=a;
    }

    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()){
      |     ^~~
bosses.cpp: In function 'int32_t main()':
bosses.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int i = (a); i < (b); i++)
      |                                       ^
bosses.cpp:59:17: note: in expansion of macro 'rep'
   59 |                 rep(i,0,visited.size()){
      |                 ^~~
bosses.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,a,b) for(int i = (a); i < (b); i++)
      |                                       ^
bosses.cpp:81:13: note: in expansion of macro 'rep'
   81 |             rep(i,0,visited.size()){
      |             ^~~

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