oj.uz

Submission #66409

# Submission time Handle Problem Language Result Execution time Memory
66409 2018-08-10T12:06:06 Z khohko Bosses (BOI16_bosses) C++17
100 / 100
 874 ms 48508 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

ll n;
ll m,k;
vector<ll> v[ARRS];
ll f[ARRS];
int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1; i<=n; i++){
		cin>>m;
		while(m--){
			cin>>k;
			v[k].pb(i);
		}
	}
	ll pas=MAX;
	for(int i=1; i<=n; i++){
		for(int i=1; i<=n; i++)f[i]=0;
		queue<pair<ll,ll> > q;
		q.push({i,1});
		ll p=0;
		while(q.size()){
			auto x=q.front();
			q.pop();
			if(f[x.fr])continue;
			f[x.fr]=1;
			p+=x.sc;
			for(auto y:v[x.fr])
				q.push({y,x.sc+1});
		}
		bool e=1;
		for(int i=1; i<=n; i++)e&=f[i];
		if(e)
		pas=min(pas,p);
	}
	cout<<pas;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 45 ms 47460 KB Output is correct
3 Correct 40 ms 47460 KB Output is correct
4 Correct 41 ms 47616 KB Output is correct
5 Correct 43 ms 47740 KB Output is correct
6 Correct 43 ms 47740 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 45 ms 47460 KB Output is correct
3 Correct 40 ms 47460 KB Output is correct
4 Correct 41 ms 47616 KB Output is correct
5 Correct 43 ms 47740 KB Output is correct
6 Correct 43 ms 47740 KB Output is correct
7 Correct 45 ms 47740 KB Output is correct
8 Correct 41 ms 47740 KB Output is correct
9 Correct 43 ms 47740 KB Output is correct
10 Correct 45 ms 47780 KB Output is correct
11 Correct 46 ms 47780 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 45 ms 47460 KB Output is correct
3 Correct 40 ms 47460 KB Output is correct
4 Correct 41 ms 47616 KB Output is correct
5 Correct 43 ms 47740 KB Output is correct
6 Correct 43 ms 47740 KB Output is correct
7 Correct 45 ms 47740 KB Output is correct
8 Correct 41 ms 47740 KB Output is correct
9 Correct 43 ms 47740 KB Output is correct
10 Correct 45 ms 47780 KB Output is correct
11 Correct 46 ms 47780 KB Output is correct
12 Correct 70 ms 48220 KB Output is correct
13 Correct 62 ms 48220 KB Output is correct
14 Correct 266 ms 48220 KB Output is correct
15 Correct 69 ms 48220 KB Output is correct
16 Correct 874 ms 48244 KB Output is correct
17 Correct 822 ms 48344 KB Output is correct
18 Correct 801 ms 48508 KB Output is correct