Submission #112651

#	Time	Username	Problem	Language	Result	Execution time	Memory
112651		Evirir	Bosses (BOI16_bosses)	C++17	100 / 100	1455 ms	1244 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<endl
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define PI 3.14159265358979323846264338327
#define INF 2e14
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 5005

int n;
vi adj[MAXN];
vi adj2[MAXN];
bool vst[MAXN];
ll sz[MAXN];
ll cnt=0;

void bfs(int r){
	queue<int> q;
	q.push(r);
	vst[r]=true;
	cnt++;
	
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v: adj[u]){
			if(!vst[v]){
				adj2[u].pb(v);
				q.push(v);
				vst[v]=true;
				cnt++;
			}
		}
	}
	//cout<<'\n';
}

void dfs(int u){
	sz[u]=1;
	for(int v: adj2[u]){
		dfs(v);
		sz[u]+=sz[v];
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	forn(i,0,n){
		int t; cin>>t;
		forn(j,0,t){
			int u; cin>>u; u--;
			adj[u].pb(i);
		}
	}
	
	ll ans=INF;
	forn(i,0,n){
		mset(vst,0);
		mset(sz,0);
		cnt=0;
		forn(j,0,n) adj2[j].clear();
		
		bfs(i);
		
		/*forn(i,0,n){
			cout<<"adj["<<i+1<<"]: ";
			for(int v: adj2[i]) cout<<v+1<<" ";
			cout<<'\n';
		}*/
		
		if(cnt!=n) continue;
		
		dfs(i);
		
		ll sum=0;
		forn(j,0,n){
			sum+=sz[j];
		}
		ans=min(ans,sum);
	}
	
	cout<<ans<<'\n';
	
	return 0;
}

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