Submission #828900

#	Time	Username	Problem	Language	Result	Execution time	Memory
828900		serifefedartar	Bosses (BOI16_bosses)	C++17	100 / 100	572 ms	660 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 300005

vector<vector<int>> graph;
ll res = 0;
int n;
bool bfs(int node) {
	int cnt = 0;
	vector<bool> vis(n+1, false);
	queue<pair<int,int>> q;
	q.push({node, 1});
	while (!q.empty()) {
		int node = q.front().f;
		int dist = q.front().s;
		q.pop();

		if (vis[node])
			continue;
		vis[node] = true;
		res += dist;
		cnt++;
		for (auto u : graph[node]) {
			if (!vis[u])
				q.push({u, dist+1});
		}
	}

	return cnt == n;
}

int main() {
    fast
    cin >> n;

    graph = vector<vector<int>>(n+1, vector<int>());
    for (int i = 1; i <= n; i++) {
    	int k; cin >> k;
    	for (int j = 0; j < k; j++) {
    		int boss_cand;
  			cin >> boss_cand;
  			graph[boss_cand].push_back(i);
    	}
    }

    ll ans = INT_MAX;
    for (int i = 1; i <= n; i++) {
    	res = 0;
   		bool control = bfs(i);
   		if (control)
   			ans = min(ans, res);
    }
    cout << ans << "\n";
}

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