Submission #340234

#	Time	Username	Problem	Language	Result	Execution time	Memory
340234		Kerim	Bosses (BOI16_bosses)	C++17	100 / 100	870 ms	1004 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>; 
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert 
#define pf push_front 
#define pb push_back
 
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
#define int ll
 
const int N = 5000+5;
vl g[N],tr[N];
int salary[N];
bool vis[N];
void solve(){
    int n;
    cin >> n;
    FOR(i,1,n+1){
        int k;
        cin >> k;
        FOR(j,1,k+1){
            int p;cin >> p;
            g[p].pb(i);
        }
    }  
    int ans=  INF;
    FOR(i,1,n+1){
        // root the tree at this node and run a dfs
        // salary[u] = sum salary[v] + 1
        FOR(j,1,n+1){
            vis[j] = 0;
            salary[j] = -1;
        }
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        salary[i] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            trav(v,g[u]){
                if(vis[v] == 0){
                    vis[v] = 1;
                    q.push(v);
                    salary[v] = salary[u] + 1;
                }
            }
        }
        int sum = 0;
        bool gg = 1;
        FOR(j,1,n+1) sum += salary[j],gg &= (salary[j] > 0);
        if(gg)
            ans = min(ans,sum); 
    }
    cout << ans << "\n";
 
}
 
signed main() {
	solve();return 0;
}

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