oj.uz

Submission #509379

# Submission time Handle Problem Language Result Execution time Memory
509379 2022-01-14T05:15:30 Z sumit_kk10 Bosses (BOI16_bosses) C++17
100 / 100
 827 ms 27912 KB 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL) 
#define ll long long
#define pb push_back
#define F first 
#define S second
using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, sum = 0;
vector<int> g[N], vis(N);
 
void solve(){
	cin >> n;
	for(int i = 1; i <= n; ++i){
		int x;
		cin >> x;
		for(int j = 0; j < x; ++j){
			int k;
			cin >> k;
			g[k].pb(i);
		}
	}
	long long ans = INT_MAX;
	for(int root = 1; root <= n; ++root){
		for(int j = 1; j <= n; ++j) vis[j] = 0;
		queue<pair<int, int> > q;
		long long sum = 1;
		q.push({root, 1});
		vis[root] = true;
		while(!q.empty()){
			int node = q.front().F, cost = q.front().S;
			q.pop();
			for(auto k : g[node]){
				if(!vis[k]){
					q.push({k, cost + 1});
					sum += cost + 1;
					vis[k] = true;
				}
			}
		}
		bool ok = 1;
		for(int i = 1; i <= n; ++i){
			if(!vis[i])
				ok = 0;
		}
		if(ok) ans = min(ans, sum);
		// cout << sum << '\n';
	}
	cout << ans << '\n';
}
 
int main() {
    fast;
    int t = 1;
    // cin >> t;
    while(t--)
    	solve();
	return 0;
}

Compilation message

bosses.cpp: In function 'int main()':
bosses.cpp:56:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   56 |     while(t--)
      |     ^~~~~
bosses.cpp:58:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   58 |  return 0;
      |  ^~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27596 KB Output is correct
2 Correct 17 ms 27596 KB Output is correct
3 Correct 15 ms 27612 KB Output is correct
4 Correct 14 ms 27604 KB Output is correct
5 Correct 14 ms 27596 KB Output is correct
6 Correct 14 ms 27672 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27596 KB Output is correct
2 Correct 17 ms 27596 KB Output is correct
3 Correct 15 ms 27612 KB Output is correct
4 Correct 14 ms 27604 KB Output is correct
5 Correct 14 ms 27596 KB Output is correct
6 Correct 14 ms 27672 KB Output is correct
7 Correct 16 ms 27708 KB Output is correct
8 Correct 15 ms 27724 KB Output is correct
9 Correct 15 ms 27724 KB Output is correct
10 Correct 15 ms 27724 KB Output is correct
11 Correct 15 ms 27692 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27596 KB Output is correct
2 Correct 17 ms 27596 KB Output is correct
3 Correct 15 ms 27612 KB Output is correct
4 Correct 14 ms 27604 KB Output is correct
5 Correct 14 ms 27596 KB Output is correct
6 Correct 14 ms 27672 KB Output is correct
7 Correct 16 ms 27708 KB Output is correct
8 Correct 15 ms 27724 KB Output is correct
9 Correct 15 ms 27724 KB Output is correct
10 Correct 15 ms 27724 KB Output is correct
11 Correct 15 ms 27692 KB Output is correct
12 Correct 16 ms 27740 KB Output is correct
13 Correct 16 ms 27852 KB Output is correct
14 Correct 197 ms 27796 KB Output is correct
15 Correct 39 ms 27740 KB Output is correct
16 Correct 656 ms 27912 KB Output is correct
17 Correct 747 ms 27852 KB Output is correct
18 Correct 827 ms 27860 KB Output is correct