oj.uz

Submission #107197

# Submission time Handle Problem Language Result Execution time Memory
107197 2019-04-22T12:51:35 Z SOIVIEONE Bosses (BOI16_bosses) C++14
100 / 100
 707 ms 5880 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define INF 1000000021
#define MOD 1000000007
#define pb push_back
#define sqr(a) (a)*(a)
#define M(a, b) make_pair(a,b)
#define F first
#define S second
#define all(x) (x.begin(), x.end())
#define deb(x) cerr << #x << " = " << x << '\n'
#define N 222222

using namespace std;
using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ld pi = 2 * acos(0.0);
template<class T> bool umin(T& a, T b){if(a>b){a=b;return 1;}return 0;}
template<class T> bool umax(T& a, T b){if(a<b){a=b;return 1;}return 0;}
template<class T, class TT> bool pal(T a, TT n){int k=0;for(int i=0;i<=n/2;i++){if(a[i]!=a[n-i-1]){k=1;break;}}return k?0:1;}

//int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

vll v[N];
ll dead[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		int x;
		cin >> x;
		while(x --)
		{
			int o;
			cin >> o;
			v[o].pb(i);
		}
	}
	ll ans = 1e17;
	for(int k = 1; k <= n; k ++)
	{
		queue<int> q;
		for(int i = 1; i <= n; i ++)
			dead[i] = 0;
		q.push(k);
		int cnt = 0;
		dead[k] = 1;
		ll res = 1;
		while(q.size())
		{
			int u = q.front();
			q.pop();
			for(auto it : v[u])
			{
				if(dead[it] == 0)
				{
					cnt ++;
					dead[it] = dead[u] + 1;
					res += dead[it];
					q.push(it);
				}
			}
		}
		if(cnt == n - 1)
			umin(ans, res);
	}
	cout << ans;





	





	getchar();
	getchar();
	return 0;
	//ios::sync_with_stdio(false);
	//cin.tie(0);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 8 ms 5476 KB Output is correct
6 Correct 8 ms 5632 KB Output is correct

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5504 KB Output is correct
2 Correct 7 ms 5504 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 7 ms 5504 KB Output is correct
5 Correct 8 ms 5476 KB Output is correct
6 Correct 8 ms 5632 KB Output is correct
7 Correct 7 ms 5504 KB Output is correct
8 Correct 7 ms 5504 KB Output is correct
9 Correct 6 ms 5632 KB Output is correct
10 Correct 9 ms 5504 KB Output is correct
11 Correct 8 ms 5504 KB Output is correct
12 Correct 11 ms 5632 KB Output is correct
13 Correct 11 ms 5760 KB Output is correct
14 Correct 165 ms 5632 KB Output is correct
15 Correct 33 ms 5752 KB Output is correct
16 Correct 680 ms 5860 KB Output is correct
17 Correct 707 ms 5852 KB Output is correct
18 Correct 654 ms 5880 KB Output is correct