Submission #338183

#	Time	Username	Problem	Language	Result	Execution time	Memory
338183		aloo123	Bosses (BOI16_bosses)	C++14	67 / 100	1514 ms	1388 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>; 
#define mp make_pair
#define f first
#define s second
 
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert 
#define pf push_front 
#define pb push_back
 
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
const int MOD = 1e9+7; // 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
#define int ll
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!

const int N = 5000+5;
vl g[N],tr[N];
int salary[N];
bool vis[N];
void dfs(int u,int p){
    salary[u] = 1;
    trav(v,tr[u]){
        if(v == p) continue;
        dfs(v,u);
        salary[u] += salary[v];
    }
}
void solve(){
    int n;
    cin >> n;
    FOR(i,1,n+1){
        int k;
        cin >> k;
        FOR(j,1,k+1){
            int p;cin >> p;
            g[p].pb(i);
        }
    }  
    int ans=  INF;
    FOR(i,1,n+1){
        // root the tree at this node and run a dfs
        // salary[u] = sum salary[v] + 1
        FOR(j,1,n+1){
            tr[j].clear();
            vis[j] = 0;
            salary[j] = -1;
        }
        queue<int> q;
        q.push(i);
        vis[i] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            trav(v,g[u]){
                if(vis[v] == 0){
                    vis[v] = 1;
                    q.push(v);
                    tr[u].pb(v);
                    tr[v].pb(u);
                }
            }
        }
        dfs(i,0);
        int sum = 0;
        bool gg = 1;
        FOR(j,1,n+1) sum += salary[j],gg &= (salary[j] > 0);
        if(gg)
            ans = min(ans,sum); 
    }
    cout << ans << "\n";

}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	// you should actually read the stuff at the bottom
	int t=1;
	// cin >> t;
	while(t--){
		solve();
	}
}
/* stuff you should look for
	* read the probem 3 more times in case of WA :)
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

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