Submission #813765

#	Time	Username	Problem	Language	Result	Execution time	Memory
813765		chanvcl123	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	596 KiB

bosses

	//#pragma gcc optimize("Ofast")
	//#pragma GCC optimization("Ofast")
	//#pragma optimize(Ofast)
	//#pragma GCC optimize("O3,unroll-loops")
	//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
	//pragma xin
	// Judges with GCC >= 12 only needs Ofast
	// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
	// MLE optimization
	// #pragma GCC optimize("conserve-stack")
	// Old judges
	// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
	// New judges. Test with assert(__builtin_cpu_supports("avx2"));
	// #pragma GCC target("arch=skylake")
	// Atcoder
	// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma"
	#include<bits/stdc++.h>
	#define F first
	#define Sc second
	#define pb push_back
	#define endl "\n"
	using namespace std;
	using ll=long long;
	ll n;
	vector<ll> adj[6005];
	ll dp[6005];
	vector<ll> g[6005];
	ll  cnt=0;
	ll sum=0;
	ll ans=1e18;
	queue<int> Q;
	void dfs(int u){
    dp[u]=1;
    ++cnt;
    for (int v: g[u]){
        dfs(v);
        dp[u]+=dp[v];
    }
    sum+=dp[u];
}
	void bfs(int source){
		sum=0;
		cnt=0;
		Q.push(source);
		bool visited[n+5]={};
		visited[source]=1;
		while(!Q.empty()){
			int u=Q.front();
			Q.pop();
			for(int v:adj[u]){
				if(visited[v]) continue;
				visited[v]=true;
				Q.push(v);
				cnt++;
				g[u].push_back(v);
			}
		}
		dfs(source);
		if(cnt==n){
			ans=min(ans,sum);
		}
		
	}
	int main(){
	   // freopen("atlanin.txt", "r", stdin);
		// freopen("atlanout.txt", "w", stdout);
		ios_base::sync_with_stdio(false);
	    cin.tie(NULL);
	    cin>>n;
	    int k;
	    int x;
	    for(int i=1;i<=n;++i){
	    	cin>>k;
	    	for(int j=1;j<=k;++j){
	    		cin>>x;
	    		adj[x].emplace_back(i);
	    	}
	    }
	    for(int i=1;i<=n;++i){
	        for(int j=1;j<=n;++j) {
	        	dp[j]=0;
	        	g[j].clear();
	        }
	        bfs(i);
	        ans=min(ans,sum);
	    }
	    cout<<ans;
	}
	

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