Submission #949956

#	Time	Username	Problem	Language	Result	Execution time	Memory
949956		huangallen	Bosses (BOI16_bosses)	C++17	100 / 100	424 ms	856 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int,int>
#define pipii pair<int,pii>
#define Graph vector<vector<int>>
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define md(x) (((x)%(mod)+(mod))%(mod))
#define MD(x,M) (((x)%(M)+(M))%(M))
#define ld long double
#define pdd pair<ld,ld>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) cout<<(#x)<<":";REP(allen,(x).size()) cout<<x[allen]<<" ";cout<<" size="<<(x).size()<<endl;
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
const int mod=1e9+7;
const int maxn=2e5+5;
const int maxv=1e5+5;
const int inf=(1ll<<62);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l,int r) {
    return uniform_int_distribution<int>(l,r)(rng);
}
Graph g;
int an=inf;
int n;
int solve(int root) {
    queue<int> q;
    q.push(root);
    vector<int> lev(n);
    lev[root]=1;
    int ret=0;
    while(q.size()) {
        int u=q.front();
        q.pop();
        ret+=lev[u];
        for(int v:g[u]) {
            if(lev[v]) continue;
            lev[v]=lev[u]+1;
            q.push(v);
        }
    }
    REP(i,n) if(!lev[i]) return inf;
    return ret;
}
signed main() {
    IOS();
    cin>>n;
    g=Graph(n);
    REP(i,n) {
        int k;cin>>k;
        REP(j,k) {
            int v;
            cin>>v;
            v--;
            g[v].pb(i);
        }
    }
    REP(i,n) an=min(an,solve(i));
    cout<<an<<'\n';
    return 0;
}
/*
4
1 4
3 1 3 4
2 1 2
1 3
*/

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