oj.uz

Submission #20996

# Submission time Handle Problem Language Result Execution time Memory
20996 2017-03-27T10:36:33 Z model_code Bosses (BOI16_bosses) C++11
100 / 100
 819 ms 2664 KB 
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

vector<int> g[10101];
int u[10101];
ll d[10101];

int n;

ll test(int x){
	queue<int> bfs;
	for (int i=1;i<=n;i++){
		u[i]=0;
		d[i]=0;
	}
	bfs.push(x);
	u[x]=1;
	d[x]=1;
	while (!bfs.empty()){
		int t=bfs.front();
		bfs.pop();
		for (int nx:g[t]){
			if (u[nx]==0){
				u[nx]=1;
				d[nx]=d[t]+1;
				bfs.push(nx);
			}
		}
	}
	ll v=0;
	for (int i=1;i<=n;i++){
		if (u[i]==0){
			return -1;
		}
		else{
			v+=d[i];
		}
	}
	return v;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	assert(n>=1&&n<=5000);
	int m=0;
	for (int i=1;i<=n;i++){
		int k;
		cin>>k;
		m+=k;
		for (int j=0;j<k;j++){
			int a;
			cin>>a;
			assert(a>=1&&a<=n&&a!=i);
			g[a].push_back(i);
		}
	}
	assert(m>=1&&m<=10000);
	ll v=-1;
	for (int i=1;i<=n;i++){
		ll asd=test(i);
		if (asd!=-1){
			if (v==-1) v=asd;
			else v=min(v, asd);
		}
	}
	cout<<v<<endl;
}

Compilation message

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2532 KB Output is correct
2 Correct 0 ms 2532 KB Output is correct
3 Correct 0 ms 2532 KB Output is correct
4 Correct 0 ms 2532 KB Output is correct
5 Correct 0 ms 2532 KB Output is correct
6 Correct 0 ms 2532 KB Output is correct
7 Correct 0 ms 2532 KB Output is correct
8 Correct 0 ms 2532 KB Output is correct
9 Correct 0 ms 2532 KB Output is correct
10 Correct 0 ms 2532 KB Output is correct
11 Correct 0 ms 2532 KB Output is correct
12 Correct 3 ms 2532 KB Output is correct
13 Correct 3 ms 2532 KB Output is correct
14 Correct 199 ms 2532 KB Output is correct
15 Correct 59 ms 2532 KB Output is correct
16 Correct 723 ms 2664 KB Output is correct
17 Correct 769 ms 2664 KB Output is correct
18 Correct 819 ms 2664 KB Output is correct