oj.uz

Submission #358892

# Submission time Handle Problem Language Result Execution time Memory
358892 2021-01-26T07:11:53 Z Bill_00 Bosses (BOI16_bosses) C++14
100 / 100
 850 ms 5356 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pp push
#define MOD 1000000007
#define INF 1e18
#define N 200005
typedef long long ll;
using namespace std;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int>adj[N];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		int k;
		cin >> k;
		while(k--){
			int c;
			cin >> c;
			adj[c].pb(i);
		}
	}
	long long ans=1e18;
	for(int i=1;i<=n;i++){
		int cnt=0;
		long long res=0;
		bool vis[5001];
		memset(vis,0,sizeof(vis));
		queue<pair<ll,ll> >q;
		q.push({(ll)i,(ll)1});
		vis[i]=1;
		while(!q.empty()){
			cnt++;
			int node=q.front().ff;
			int height=q.front().ss;
			q.pop();
			res+=height;
			for(int j:adj[node]){
				if(vis[j]==0){
					vis[j]=1;
					q.push({j,height+1});
				}
			}
		}
		if(cnt==n) ans=min(ans,res);
	}
	cout << ans;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4972 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 5 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Correct 8 ms 5100 KB Output is correct
13 Correct 7 ms 5100 KB Output is correct
14 Correct 186 ms 5100 KB Output is correct
15 Correct 7 ms 5100 KB Output is correct
16 Correct 687 ms 5356 KB Output is correct
17 Correct 850 ms 5356 KB Output is correct
18 Correct 837 ms 5356 KB Output is correct