oj.uz

Submission #596578

# Submission time Handle Problem Language Result Execution time Memory
596578 2022-07-14T21:07:12 Z 1zaid1 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 1112 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long

const int M = 1e4+2;
vector<int> node[M], nod[M];
bitset<5005> vis;
int n;

int check(int s) {
    vis = 0;
    vis[s] = true;
    queue<int> q;
    q.push(s);
    int cnt = 0;
    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (int i:node[f]) {
            if (!vis[i]) {
                vis[i] = true;
                q.push(i);
            }
        } cnt++;
    } return cnt;
}

pair<int, int> dfs(int s) {
    int a = 0, b = 0;
    vis[s] = true;
    for (int i:nod[s]) {
        if (!vis[i]) {
            auto [x, y] = dfs(i);
            a += x; b += y;
        }
    } return {a+1, b+a+1};
}

int solve(int s) {
    vis = 0;
    vis[s] = true;
    queue<int> q;
    q.push(s);
    for (int i = 1; i <= n; i++) nod[i].clear();
    while (!q.empty()) {
        int f = q.front(); q.pop();
        for (int i:node[f]) {
            if (!vis[i]) {
                vis[i] = true;
                nod[f].push_back(i);
                q.push(i);
            }
        }
    } vis = 0;
    return dfs(s).second;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;

        for (int j = 1; j <= m; j++) {
            int a;
            cin >> a;
            node[a].push_back(i);
        }
    }

    int mn = INT_MAX;
    for (int i = 1; i <= n; i++) {
        if (check(i) == n) mn = min(mn, solve(i));
    } cout << mn << endl;

    return 0;
}
/*
4
1 4
3 1 3 4
2 1 2
1 3

*/

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 0 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 0 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 5 ms 852 KB Output is correct
14 Correct 104 ms 1112 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 477 ms 912 KB Output is correct
17 Execution timed out 1544 ms 1108 KB Time limit exceeded
18 Halted 0 ms 0 KB -