oj.uz

Submission #58321

# Submission time Handle Problem Language Result Execution time Memory
58321 2018-07-17T13:34:42 Z jovan_b Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1160 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

typedef long long ll;
typedef long double ld;

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

int cost;
int kost[5005];

bool visited[5005];

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

void dfs(int v){
    for(auto c : drvo[v]){
        dfs(c);
        kost[v] += kost[c];
    }
    cost += kost[v];
}

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;
        bfs(i);
        int mk = 0;
        for(int j=1; j<=n; j++) if(!visited[j]) mk = 1;
        if(mk == 1) continue;
        dfs(i);
        mincost = min(mincost, cost);
    }
    cout << mincost;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 2 ms 740 KB Output is correct
5 Correct 3 ms 740 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 4 ms 764 KB Output is correct
8 Correct 4 ms 808 KB Output is correct
9 Correct 3 ms 808 KB Output is correct
10 Correct 3 ms 808 KB Output is correct
11 Correct 3 ms 824 KB Output is correct
12 Correct 7 ms 872 KB Output is correct
13 Correct 6 ms 1004 KB Output is correct
14 Correct 280 ms 1104 KB Output is correct
15 Correct 77 ms 1104 KB Output is correct
16 Correct 937 ms 1160 KB Output is correct
17 Execution timed out 1563 ms 1160 KB Time limit exceeded
18 Halted 0 ms 0 KB -