Submission #442232

#	Time	Username	Problem	Language	Result	Execution time	Memory
442232		aryan12	Bosses (BOI16_bosses)	C++17	100 / 100	782 ms	668 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 5010;
vector<int> g[N];

void Solve() {
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		int len;
		cin >> len;
		for(int j = 0; j < len; j++) {
			int x;
			cin >> x;
			g[x].push_back(i);
		}
	}
	int ans = INT_MAX;
	for(int root = 1; root <= n; root++) {
		int depth[n + 1];
		for(int i = 0; i <= n; i++) {
			depth[i] = -1;
		}
		queue<int> q;
		q.push(root);
		depth[root] = 0;
		int cnt = 1, curans = n;
		while(!q.empty()) {
			int node = q.front();
			curans += depth[node];
			q.pop();
			for(int i = 0; i < g[node].size(); i++) {
				if(depth[g[node][i]] == -1) {
					q.push(g[node][i]);
					depth[g[node][i]] = depth[node] + 1;
					cnt++;
				}
			}
		}
		if(cnt != n) {
			continue;
		}
		ans = min(ans, curans);
	}
	cout << ans << "\n";
}

int32_t main() {
	//auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	//auto end = std::chrono::high_resolution_clock::now();
    //auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'void Solve()':
bosses.cpp:36:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int i = 0; i < g[node].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~

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