Submission #1102559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102559		YFHHFY	Bosses (BOI16_bosses)	C++14	22 / 100	1 ms	336 KiB

bosses

#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string 
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x)           (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define sep " "
#define F first
#define X first
#define S second
#define Y second
using namespace std;
typedef pair <int , int> pii;
const ll maxn = 5e2 + 5 ;
const int Lg = 23;
const ll inf = 1e9 ;
vi g[maxn], c[maxn];
bool use[maxn];
int cu = 0;
int dfs(int v , int p = -1){
    int x = 0;
    for (int to : c[v]){
        if (to == p) continue;
        x += dfs(to , v);
    }
    cu += x+1;
    return x+1;
}
void solve (){
    int n;
    cn >> n;
    pii mb = {-inf , -inf};
    for (int i = 1 ; i <= n ; i ++){
        int k; cn >> k;
        for (int j = 0 ; j < k ; j ++){
            int p;
            cn >> p;
            g[p].pb(i);
            mb = max (mb , {(int)g[p].sz() , p});
        }
    }
    int ans = inf;
    for (int i = 1 ; i <= n ; i ++){
        if (g[i].sz() == 0) continue;
        if (abs((int)g[i].sz() - mb.F) > 1) continue;
        for (int j = 1 ; j <= n ; j++) c[j].resize(0);
        queue <int> q;
        q.push(i);
        memset(use, 0 , sizeof use);
        use[i] = 1;
        int h = 1;
        while (SZ(q)){
            int v = q.front(); q.pop();
            for (auto to : g[v]){
                if (use[to] == 1) continue;
                c[v].pb(to);
                q.push(to);
                use[to] = 1;
                h++;
            }
        }
        if ( h == n){
            cu = 0;
            dfs(i);
            ans = min (ans , cu);
        }
    }
    ct << ans << endl;
}
mata main(){
    tizoboz;
    int tt = 1;
    // cn >> tt;
    while (tt--){
        solve();
    }
    return 0;
}

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