Submission #813753

#	Time	Username	Problem	Language	Result	Execution time	Memory
813753		dijbkr	Bosses (BOI16_bosses)	C++14	0 / 100	0 ms	468 KiB

bosses

#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[5005];
ll dp[5005];
vector<ll> g[5005];
ll  cnt=0;
ll sum=0;
ll ans=INT_MAX;
queue<int> Q;
int dfs(int u){
	//dp[u]=1;
     for(auto v:g[u]){
     	dfs(v);
     	dp[u]+=dp[v];
     }
     return dp[u];
}
void bfs(int source){
   for (int i=1; i<=n; i++) {
      dp[i]=1;
   }
	sum=0;
	cnt=0;
	Q.push(source);
	bool visited[n+5]={};
	visited[source]=1;
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		cnt++;
		for(int v:adj[u]){
			if(visited[v]) continue;
			visited[v]=true;
			Q.push(v);
			g[u].push_back(v);
		}
	}
	if(cnt==n){
		dfs(source);
		for(int i=1;i<=n;++i) sum+=dp[i];
	}
}
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