Submission #947868

#	Time	Username	Problem	Language	Result	Execution time	Memory
947868		koukirocks	Bosses (BOI16_bosses)	C++17	100 / 100	433 ms	5464 KiB

bosses

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;

int n;
vector<int> G[MAX];

int main() {
	speed;
	cin>>n;
	for (int i=1;i<=n;i++) {
		int k;
		cin>>k;
		while (k--) {
			int v;
			cin>>v;
			G[v].push_back(i);
		}
	}
	ll ans=oo;
	for (int st=1;st<=n;st++) {
		queue<int> BFS;
		vector<int> dis(n+1,0);
		vector<bool> vis(n+1,0);
		vis[st]=true;
		dis[st]=1;
		BFS.push(st);
		int ttl=0;
		while (!BFS.empty()) {
			int v=BFS.front();
			ttl++;
			BFS.pop();
//			cout<<v<<" v\n";
			for (int i:G[v]) {
				if (vis[i]) continue;
				vis[i]=true;
				dis[i]=dis[v]+1;
				BFS.push(i);
			}
		}
		if (ttl!=n) continue;
		ll now=0;
		for (int i=1;i<=n;i++) now+=dis[i];
		ans=min(ans,now);
	}
	cout<<ans<<"\n";
	return 0;
}

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