Submission #723323

#	Time	Username	Problem	Language	Result	Execution time	Memory
723323		nicky4321	Bosses (BOI16_bosses)	C++14	100 / 100	1323 ms	50096 KiB

bosses

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
vi child[MAX], edge[MAX];
int vis[MAX], k[MAX], n, total;

int dfs(int now, int from){
    int sum = 1;
    for(int i : edge[now]){
        if(i == from)
            continue;
        sum += dfs(i, now);
    }
    total += sum;
    return sum;
}

int bfs(int x){
    for(int i = 1;i <= n;i++){
        vis[i] = 0;
        edge[i].clear();
    }
    queue<int> q;
    q.push(x);
    vis[x] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pop();
        for(int i : child[now]){
            if(!vis[i]){
                edge[now].PB(i);
                q.push(i);
                vis[i] = 1;
            }
        }
    }
    for(int i = 1;i <= n;i++)
        if(!vis[i])
            return 2e9;
    total = 0;
    dfs(x, x);
    return total;
}

void solve(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> k[i];
        for(int j = 1;j <= k[i];j++){
            int x;
            cin >> x;
            child[x].PB(i);
        }
    }
    int ans = 2e9;
    for(int i = 1;i <= n;i++){
        ans = min(ans, bfs(i));
    }
    cout << ans << '\n';
}

int main(){
    IOS
    // CASE
        solve();
    return 0;
}

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