oj.uz

Submission #884347

# Submission time Handle Problem Language Result Execution time Memory
884347 2023-12-07T07:56:56 Z vjudge1 Bosses (BOI16_bosses) C++17
0 / 100
 1 ms 700 KB 
/*
#pragma GCC optimize("fast-math")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
*/
#include<bits/stdc++.h>
     
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
#define pb              push_back
#define F               first
#define S               second
#define len(x)          (int)x.size()
#define all(x)          x.begin(),x.end()
#define file            freopen("txt.in", "r", stdin);freopen("txt.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; return 0;}
#define int             long long

const int N = 5e3 + 5, LG = 21, MOD = 1e9+7;// 998244353
const ll inf =  4557430888798830399;

int n, ans, dist[N], cnt;
vector<int> g[N], G[N];
queue<int> q;
bitset<N> mark;

signed main() { 
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int sz, v;
        cin >> sz;
        for(int j = 0; j < sz; ++j) {
            cin >> v;
            g[v].pb(i);
        }
    }

    ll ans = inf;
    for(int i = 1; i <= n; ++i) {
        cnt = 1;
        q.push(i);
        dist[i] = 1;
        while(!q.empty()){
            int v = q.front();
            mark[v] = 1;
            q.pop();
            for(int u : g[v]) {
                if(!mark[u]) {
                    dist[u] = dist[v] + 1;
                    cnt += dist[u];
                    mark[u] = 1;
                    q.push(u);
                }
            }
        }
        ans = min(ans, cnt);
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            mark[i]= 0;
        }
    }

    cout << ans;
    
    
    return 0;
}

Subtask #1
0 / 22.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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