oj.uz

Submission #695115

# Submission time Handle Problem Language Result Execution time Memory
695115 2023-02-04T18:06:48 Z Farhan_HY Bosses (BOI16_bosses) C++14
100 / 100
 642 ms 24140 KB 
#include <bits/stdc++.h>
#define int long long
#define float double
#define pb push_back
#define F first
#define S second
#define T int t; cin >> t; while(t--)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
/// Benzema is the best player in the world
const int N = 1e6 + 6;
const int M = 1e3 + 3;
const int mod = 1e9 + 7;
const int inf = 1e9;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int LOG = 28;
int n, cnt[N];
vector<int> adj[N];
queue<int> q;

pair<int, int> bfs(int node) {
    int count = 1;
    q.push(node);
    cnt[node] = 1;
    int ans = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto x: adj[u]) {
            if (cnt[x]) continue;
            cnt[x] = cnt[u] + 1;
            ans += cnt[x];
            count++;
            q.push(x);
        }
    }
    return {ans, count};
}

main() {
    IOS
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for(int j = 1; j <= k; j++) {
            int u;
            cin >> u;
            adj[u].push_back(i);
        }
    }
    int ans = inf;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) cnt[j] = 0;
        pair<int, int> p = bfs(i);
        if (p.S == n) ans = min(ans, p.F);
    }
    cout << ans;
}

Compilation message

bosses.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main() {
      | ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 13 ms 23812 KB Output is correct
4 Correct 12 ms 23812 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 13 ms 23812 KB Output is correct
4 Correct 12 ms 23812 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 11 ms 23816 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 12 ms 23760 KB Output is correct
11 Correct 13 ms 23768 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 11 ms 23816 KB Output is correct
3 Correct 13 ms 23812 KB Output is correct
4 Correct 12 ms 23812 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 11 ms 23816 KB Output is correct
8 Correct 11 ms 23764 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 12 ms 23760 KB Output is correct
11 Correct 13 ms 23768 KB Output is correct
12 Correct 15 ms 23960 KB Output is correct
13 Correct 14 ms 24020 KB Output is correct
14 Correct 125 ms 23972 KB Output is correct
15 Correct 18 ms 23892 KB Output is correct
16 Correct 493 ms 24080 KB Output is correct
17 Correct 597 ms 24140 KB Output is correct
18 Correct 642 ms 24056 KB Output is correct