Submission #884359

#	Time	Username	Problem	Language	Result	Execution time	Memory
884359		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	425 ms	756 KiB

bosses

/*
#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];
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);
                }
        }
        if(mark.count() != n) {
            mark.reset();
            continue;
        }
        ans = min(ans, cnt);
        mark.reset();
    }

    cout << ans;
    
    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:60:25: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   60 |         if(mark.count() != n) {
      |            ~~~~~~~~~~~~~^~~~

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33