oj.uz

답안 #764348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764348 2023-06-23T10:50:57 Z Ellinor Bosses (BOI16_bosses) C++14
100 / 100
 605 ms 620 KB 
#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

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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 6 ms 400 KB Output is correct
13 Correct 5 ms 400 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 3 ms 568 KB Output is correct
17 Correct 590 ms 620 KB Output is correct
18 Correct 605 ms 612 KB Output is correct