Submission #711750

#	Time	Username	Problem	Language	Result	Execution time	Memory
711750		aedmhsn	Bosses (BOI16_bosses)	C++17	0 / 100	2 ms	340 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 
 
#define boost() ios_base::sync_with_stdio(false); cin.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1);

const int mxN=5e3+5;

bool cool[mxN][mxN];

bool vis[mxN];

ll temp=0;

ll dfs(int node){
    ll sum=0;
    vis[node]=1;
    vector <int> children;
    for(int i=1; i<=5000; i++){
        if(cool[node][i] && !vis[i]){
            vis[i]=1;
            children.push_back(i);
        }
    }
    for(auto x:children){
        sum += dfs(x);
    }
    temp += sum+1;
    return sum+1;
}

int main(){ 

    boost();
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        int q;
        cin >> q;
        while(q--){
            int x;
            cin >> x;
            cool[x][i]=1;
        }
    }
    ll ans=INT_MAX;
    for(int i=1; i<=n; i++){
        ms(vis, 0);
        temp=0;
        dfs(i);
        bool valid=true;
        for(int i=1; i<=n; i++){
            if(!vis[i])
                valid=false;
        }
        if(valid)
            ans = min(ans, temp);
    }
    cout << ans;

}

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