oj.uz

Submission #442227

# Submission time Handle Problem Language Result Execution time Memory
442227 2021-07-07T10:10:49 Z aryan12 Bosses (BOI16_bosses) C++17
67 / 100
 6 ms 572 KB 
#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 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();
			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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 6 ms 572 KB Output isn't correct
13 Halted 0 ms 0 KB -