oj.uz

Submission #648049

# Submission time Handle Problem Language Result Execution time Memory
648049 2022-10-05T07:47:26 Z mychecksedad Bosses (BOI16_bosses) C++17
100 / 100
 1309 ms 47740 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, d;
ll S;
vector<bool> vis;
vector<int> g[N], r[N];
ll dfs(int v){
    if(r[v].empty()){
        S++;
        return 1;
    }
    ll s = 1;
    for(int u: r[v]) s += dfs(u);
    S += s;
    return s;
}
void bfs(int s){
    queue<int> q;
    vis[s] = 1;
    q.push(s);
    while(!q.empty()){
        int v = q.front(); q.pop();
        for(int u: g[v]){
            if(!vis[u]){
                vis[u] = 1;
                q.push(u);
                r[v].pb(u);
            }
        }
    }
    dfs(s);
}
void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        int d; cin >> d;
        for(int j = 0; j < d; ++j){
            int x; cin >> x; g[x].pb(i);
        }
    }
    ll best = 1e18;
    for(int i = 1; i <= n; ++i){
        S = 0;
        vis.clear();
        vis.resize(n+1);
        bfs(i);
        bool ok = 1;
        for(int i = 1; i <= n; ++i) ok &= vis[i], r[i].clear();
        if(ok)
            best = min(best, S);
    }
    cout << best;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:77:16: warning: unused variable 'aa' [-Wunused-variable]
   77 |     int T = 1, aa;
      |                ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47188 KB Output is correct
2 Correct 32 ms 47168 KB Output is correct
3 Correct 34 ms 47216 KB Output is correct
4 Correct 31 ms 47236 KB Output is correct
5 Correct 33 ms 47176 KB Output is correct
6 Correct 34 ms 47272 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47188 KB Output is correct
2 Correct 32 ms 47168 KB Output is correct
3 Correct 34 ms 47216 KB Output is correct
4 Correct 31 ms 47236 KB Output is correct
5 Correct 33 ms 47176 KB Output is correct
6 Correct 34 ms 47272 KB Output is correct
7 Correct 28 ms 47188 KB Output is correct
8 Correct 28 ms 47188 KB Output is correct
9 Correct 24 ms 47188 KB Output is correct
10 Correct 23 ms 47276 KB Output is correct
11 Correct 24 ms 47188 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47188 KB Output is correct
2 Correct 32 ms 47168 KB Output is correct
3 Correct 34 ms 47216 KB Output is correct
4 Correct 31 ms 47236 KB Output is correct
5 Correct 33 ms 47176 KB Output is correct
6 Correct 34 ms 47272 KB Output is correct
7 Correct 28 ms 47188 KB Output is correct
8 Correct 28 ms 47188 KB Output is correct
9 Correct 24 ms 47188 KB Output is correct
10 Correct 23 ms 47276 KB Output is correct
11 Correct 24 ms 47188 KB Output is correct
12 Correct 30 ms 47420 KB Output is correct
13 Correct 27 ms 47444 KB Output is correct
14 Correct 302 ms 47556 KB Output is correct
15 Correct 62 ms 47576 KB Output is correct
16 Correct 1049 ms 47740 KB Output is correct
17 Correct 1306 ms 47656 KB Output is correct
18 Correct 1309 ms 47656 KB Output is correct