Submission #442228

#	Time	Username	Problem	Language	Result	Execution time	Memory
442228		aryan12	Bosses (BOI16_bosses)	C++17	67 / 100	1551 ms	1004 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 = 15010;
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 par[n + 1], inedge[n + 1];
		bool vis[n + 1];
		for(int i = 0; i <= n; i++) {
			par[i] = -1;
			inedge[i] = 0;
			vis[i] = false;
		}
		queue<int> q;
		q.push(root);
		vis[root] = true;
		int cnt = 1;
		while(!q.empty()) {
			int node = q.front();
			q.pop();
			for(int i = 0; i < g[node].size(); i++) {
				if(vis[g[node][i]]) {
					continue;
				}
				vis[g[node][i]] = true;
				cnt++;
				q.push(g[node][i]);
				par[g[node][i]] = node;
				inedge[node]++;
			}
		}
		if(cnt != n) {
			continue;
		}
		int totalAns[n + 1];
		for(int i = 1; i <= n; i++) {
			totalAns[i] = 1;
			if(inedge[i] == 0) {
				q.push(i);
			}
		}
		int curans = 0;
		while(!q.empty()) {
			int node = q.front(); 
			curans += totalAns[node];
			q.pop();
			if(node == root) {
				continue;
			}
			inedge[par[node]]--;
			if(inedge[par[node]] == 0) {
				q.push(par[node]);
			}
			totalAns[par[node]] += totalAns[node];
		}
		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:38: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]
   38 |    for(int i = 0; i < g[node].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~

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