oj.uz

Submission #723323

# Submission time Handle Problem Language Result Execution time Memory
723323 2023-04-13T15:31:00 Z nicky4321 Bosses (BOI16_bosses) C++14
100 / 100
 1323 ms 50096 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
vi child[MAX], edge[MAX];
int vis[MAX], k[MAX], n, total;

int dfs(int now, int from){
    int sum = 1;
    for(int i : edge[now]){
        if(i == from)
            continue;
        sum += dfs(i, now);
    }
    total += sum;
    return sum;
}

int bfs(int x){
    for(int i = 1;i <= n;i++){
        vis[i] = 0;
        edge[i].clear();
    }
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i : child[now]){
            if(!vis[i]){
                edge[now].PB(i);
                q.push(i);
                vis[i] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++)
        if(!vis[i])
            return 2e9;
    total = 0;
    dfs(x, x);
    return total;
}

void solve(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> k[i];
        for(int j = 1;j <= k[i];j++){
            int x;
            cin >> x;
            child[x].PB(i);
        }
    }
    int ans = 2e9;
    for(int i = 1;i <= n;i++){
        ans = min(ans, bfs(i));
    }
    cout << ans << '\n';
}

int main(){
    IOS
    // CASE
        solve();
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49492 KB Output is correct
2 Correct 26 ms 49492 KB Output is correct
3 Correct 26 ms 49556 KB Output is correct
4 Correct 27 ms 49492 KB Output is correct
5 Correct 23 ms 49532 KB Output is correct
6 Correct 25 ms 49620 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49492 KB Output is correct
2 Correct 26 ms 49492 KB Output is correct
3 Correct 26 ms 49556 KB Output is correct
4 Correct 27 ms 49492 KB Output is correct
5 Correct 23 ms 49532 KB Output is correct
6 Correct 25 ms 49620 KB Output is correct
7 Correct 24 ms 49492 KB Output is correct
8 Correct 26 ms 49520 KB Output is correct
9 Correct 26 ms 49576 KB Output is correct
10 Correct 25 ms 49568 KB Output is correct
11 Correct 25 ms 49552 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49492 KB Output is correct
2 Correct 26 ms 49492 KB Output is correct
3 Correct 26 ms 49556 KB Output is correct
4 Correct 27 ms 49492 KB Output is correct
5 Correct 23 ms 49532 KB Output is correct
6 Correct 25 ms 49620 KB Output is correct
7 Correct 24 ms 49492 KB Output is correct
8 Correct 26 ms 49520 KB Output is correct
9 Correct 26 ms 49576 KB Output is correct
10 Correct 25 ms 49568 KB Output is correct
11 Correct 25 ms 49552 KB Output is correct
12 Correct 29 ms 49700 KB Output is correct
13 Correct 28 ms 49640 KB Output is correct
14 Correct 214 ms 49932 KB Output is correct
15 Correct 48 ms 49748 KB Output is correct
16 Correct 681 ms 50068 KB Output is correct
17 Correct 1323 ms 50096 KB Output is correct
18 Correct 1305 ms 49984 KB Output is correct