제출 #1275794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275794		itsKiaRash	Bosses (BOI16_bosses)	C++20	100 / 100	748 ms	1096 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds; // find_by_order   order_of_key
// template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
// #pragma GCC optimize ("O2,unroll-loops")
// #pragma GCC optimize ("Ofast")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define int ll
#define FAST_IO (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define file_init freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define testc int ttt;cin>>ttt;while(ttt--)
#define alll(x)	(x).begin(),(x).end()
#define pqi priority_queue<pii, vector<pii>, greater<pii>>
#define endl '\n'
#define pb push_back
#define ins insert
#define pii pair<int, int>
#define ff first
#define ss second
#define bg begin
#define rbg rbegin
#define sz size()
#define mset(x,y) memset(x,y,sizeof(x))
#define clr clear()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define vci vector<int>
#define sti set<int>
#define nl cout<<'\n'
#define upb upper_bound
#define lrb lower_bound
//ll pw(ll a,ll b){ll res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
const ll inf = 1e18 + 18;
const int maxn = 5e3 + 7, mod = 1e9 + 7; //998244353
int n, ans, sum;
vci adj[maxn], nei[maxn];
int dp[maxn], par[maxn];
bool vis[maxn];
void bfs(int a){
    vis[a] = true;
    queue<int> q; q.push(a);
    while(q.sz){
        int x = q.front(); q.pop();
        for(int item : nei[x]) if(!vis[item]){
            vis[item] = true; adj[x].pb(item); q.push(item);
        }
    }
}
void dfs(int u, int par = 0){
    dp[u] = 1;
    for(int v : adj[u]) if(v != par){
        dfs(v, u); dp[u] += dp[v];
    }
    sum += dp[u];
}

int32_t main(){
    FAST_IO
    cin >> n ; ans = inf;
    for(int i = 1, k ; i <= n ; i ++){
        cin >> k ;
        for(int j = 1, ki ; j <= k ; j ++){
            cin >> ki ; nei[ki].pb(i);
        }
    }
    for(int i = 1 ; i <= n ; i ++){
        mset(vis, 0); mset(par, 0); mset(dp, 0); sum = 0;
        for(int j = 1 ; j <= n ; j ++) adj[j].clr;
        bfs(i); bool flag = true;
        for(int j = 1 ; j <= n ; j ++) if(!vis[j]) {flag = false; break;}
        if(!flag) continue;
        dfs(i); ans = min(ans, sum);
    }
    cout << ans << endl;
    
    return 0;
}

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