oj.uz

Submission #838882

# Submission time Handle Problem Language Result Execution time Memory
838882 2023-08-28T04:57:03 Z vjudge1 Bosses (BOI16_bosses) C++17
0 / 100
 0 ms 352 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <bits/stdc++.h>
 
#define int long long 
#define pb push_back
#define ui unsigned int
#define ld long double
#define pl pair<long long int,  long long int>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first    
#define ss second
#define sz size()
#define all(x) x.begin(), x.end()
 
using namespace std;
 
const int maxn = 1e5 + 11;
const int inf = 1e18 + 1;
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int dx[] = {-1, 0, 0, 1, -1, -1, 1, 1};
const int dy[] = {0, -1, 1 , 0, -1, 1, -1, 1};
const double eps = 1e-10;

int used[5001];
vector<int> g[5001];
int d[5001];
int cnt;

void dfs(int v) {
    used[ v ] = 1;

    cnt += d[ v ];

    for(auto to : g[ v ]) {
        if(!used[ to ]) {
            d[ to ] = d[ v ] + 1;
            dfs( to );
        }
    }
}

void solve() {
    int n;

    cin >> n;

    for(int i = 1; i <= n; i++) {
        int k;

        cin >> k;

        for(int j = 1; j <= k; j++) {
            int x;

            cin >> x;

            g[ x ].pb( i );
        }
    }   
    int ans = inf;

    for(int i = 1; i <= n; i++) {
        cnt = 0;
        d[ i ] = 1;
        dfs( i );
        for(int j = 1; j <= n; j++) {
            if(!used[ j ]) {
                cnt = inf;
            }
            used[ j ] = 0;
            d[ j ] = 0;
        }
        ans = min(ans, cnt);
    }
    cout << ans;
}
    
signed main() {
    // freopen("sum.in", "r", stdin); 
    // freopen("sum.out", "w", stdout);
 
    boost;      

    int tt = 1;

    // cin >> tt;

    for(int i = 1; i <= tt; i++) {
        // cout << "Case " << i << ":\n";
        solve();    
    }           
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -