Submission #950305

#	Time	Username	Problem	Language	Result	Execution time	Memory
950305		LittleOrange	Bosses (BOI16_bosses)	C++17	100 / 100	598 ms	1484 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<vector<ll>> ch(n);
    for(ll i = 0;i<n;i++){
        ll k;
        cin >> k;
        while(k--){
            ll p;
            cin >> p;
            ch[p-1].push_back(i);
        }
    }
    ll ans = big;
    for(ll rt = 0;rt<n;rt++){
        //cout << "Try " << rt+1 << "\n";
        vector<ll> u(n,0),p(n,rt);
        deque<ll> q;
        q.push_back(rt);
        u[rt] = 1;
        vector<ll> v;
        while(!q.empty()){
            v.push_back(q.front());
            ll i = q.front();q.pop_front();
            for(ll j : ch[i]) if(!u[j]){
                //cout << i+1 << "->" << j+1 << "\n";
                u[j] = 1;
                p[j] = i;
                q.push_back(j);
            }
        }
        if(v.size()<n) continue;
        reverse(v.begin(),v.end());
        vector<ll> h(n,1);
        for(ll i : v){
            if(p[i]!=i) h[p[i]] += h[i];
        }
        //for(ll i = 0;i<n;i++) cout << p[i] << " \n"[i+1==n];
        //for(ll i = 0;i<n;i++) cout << h[i] << " \n"[i+1==n];
        ll cur = 0;
        for(ll i : h) cur += i;
        ans = min(ans,cur);
    }
    cout << ans << "\n";
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:37:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   37 |         if(v.size()<n) continue;
      |            ~~~~~~~~^~

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