Submission #1277621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277621		atillama	Bosses (BOI16_bosses)	C++20	67 / 100	1593 ms	1248 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>> mp(n + 1);
    rep(i, 1, n){
        int k; cin >> k;
        rep(j, 1, k){
            int e; cin >> e;
            mp[e].pb(i);
        }
    }
    int ans = INF;
    rep(i, 1, n){ // root node
        vector<vector<int>> adj(n + 1);
        vector<bool> visited(n + 1, false);
        queue<int> q;
        vector<int> v;
        q.push(i);
        visited[i] = true;
        while(q.size()){
            int from = q.front();
            q.pop();
            v.pb(from);
            for(int to : mp[from]){
                if(visited[to]) continue;
                adj[from].pb(to);
                q.push(to);
                visited[to] = true;
            }
        }
        bool bl = true;
        rep(i, 1, n) bl &= visited[i];
        if(!bl) continue;
        vector<int> x(n + 1);
        reverse(v.begin(), v.end());
        for(int j : v){
            for(int to : adj[j]){
                x[j] += x[to];
            }
            x[j]++;
        }
        int cur = 0;
        rep(j, 1, n) cur += x[j];
        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: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33