oj.uz

Submission #66408

# Submission time Handle Problem Language Result Execution time Memory
66408 2018-08-10T12:04:27 Z khohko Bosses (BOI16_bosses) C++17
0 / 100
 41 ms 47588 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});
		}
		pas=min(pas,p);
	}
	cout<<pas;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47352 KB Output is correct
2 Correct 41 ms 47588 KB Output is correct
3 Incorrect 40 ms 47588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47352 KB Output is correct
2 Correct 41 ms 47588 KB Output is correct
3 Incorrect 40 ms 47588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47352 KB Output is correct
2 Correct 41 ms 47588 KB Output is correct
3 Incorrect 40 ms 47588 KB Output isn't correct
4 Halted 0 ms 0 KB -