Submission #1277632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277632		atillama	Bosses (BOI16_bosses)	C++20	0 / 100	0 ms	332 KiB

bosses

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define double long double
#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cout << #x << " = " << x << '\n';
#define vdebug(a) cout << #a << " = "; for(auto x : a) cout << x << " "; cout << '\n';

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> indexed_pair_set;

const double eps = 1e-9;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
const int INF = 1e18;

void solve(){
    int n; cin >> n;
    vector<vector<int>> adj(n + 1);
    rep(i, 1, n){
        int k; cin >> k;
        rep(j, 1, k){
            int e; cin >> e;
            adj[e].pb(i);
        }
    }
    int ans = INF;
    rep(i, 1, n){ // root node
        vector<bool> visited(n + 1, false);
        queue<pii> q;
        q.push({i, 0});
        visited[i] = true;
        int cur = 0;
        while(q.size()){
            int from = q.front().F;
            int d = q.front().S;
            q.pop();
            cur += 1 + d;
            for(int to : adj[from]){
                if(visited[to]) continue;
                q.push({to, d + 1});
                visited[to] = true;
            }
        }
        bool bl = true;
        rep(j, 1, n) bl &= visited[j];
        if(!bl) continue;
        ans = min(ans, cur);
        cout << i << " " << cur << '\n';
    }
    cout << ans << '\n';
}

signed main(){
    fastio;
    solve();
}

/*
    freopen("x.in", "r", stdin);
    freopen("x.out", "w", stdout);
*/

//atilla

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