oj.uz

Submission #437706

# Submission time Handle Problem Language Result Execution time Memory
437706 2021-06-26T22:24:57 Z jovan_b Bosses (BOI16_bosses) C++17
100 / 100
 1112 ms 964 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

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

typedef long long ll;
typedef long double ld;

vector <int> drvo[5005];
vector <int> graf[5005];

int cost;
int kost[5005];

bool visited[5005];

int mk;

void bfs(int v){
    visited[v] = true;
    queue <pair <int, int>> q;
    q.push({v, 1});
    while(!q.empty()){
        mk++;
        int x = q.front().first;
        int y = q.front().second;
        cost += y;
        q.pop();
        for(auto c : graf[x]){
            if(!visited[c]){
                drvo[x].push_back(c);
                visited[c] = 1;
                q.push({c, y+1});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        for(int j=1; j<=x; j++){
            int a;
            cin >> a;
            graf[a].push_back(i);
        }
    }
    int mincost = 1000000000;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            visited[j] = 0;
            kost[j] = 1;
            drvo[j].clear();
        }
        cost = 0;
        mk = 0;
        bfs(i);
        if(mk != n) continue;
        mincost = min(mincost, cost);
    }
    cout << mincost << "\n";
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 696 KB Output is correct
13 Correct 4 ms 716 KB Output is correct
14 Correct 239 ms 760 KB Output is correct
15 Correct 35 ms 716 KB Output is correct
16 Correct 824 ms 908 KB Output is correct
17 Correct 1112 ms 956 KB Output is correct
18 Correct 1108 ms 964 KB Output is correct