oj.uz

Submission #388236

# Submission time Handle Problem Language Result Execution time Memory
388236 2021-04-10T15:53:28 Z soroush Bosses (BOI16_bosses) C++17
100 / 100
 1182 ms 908 KB 
//*
//#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5010;
const ll mod = 1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n;
vector < int > in[maxn];
bool mark[maxn];
int sz[maxn];
int q[maxn] , l , r;
vector < int > adj[maxn];

void dfs(int v){
	sz[v] = 1;
	for(auto u : adj[v])
		dfs(u) , sz[v] += sz[u];
}

int solve(int v){
	l = r = 0;
	ms(mark , 0);
	for(int i = 1 ; i <= n ; i ++)adj[i].clear();
	q[r++] = v;
	mark[v] = 1;
	int cnt = 1;
	while(l < r){
		int v = q[l++];
		for(auto u : in[v])if(!mark[u])
			mark[u] = 1, cnt++ , q[r++] = u , adj[v].pb(u);
	}
	if(cnt ^ n)return 1e9;
	dfs(v);
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++)ans += sz[i];
	return ans;
}

int32_t main(){
	migmig;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		int k;
		cin >> k;
		for(int j = 0 ; j < k ; j ++){
			int v;
			cin >> v;
			in[v].pb(i);
		}
	}
	//in-tree , sigma sz[v] min she
	int ans = 1e9;
	for(int i = 1 ; i <= min(n, 2500) ; i ++)
		ans = min(ans , solve(i));
	for(int i = n ; i >= 3500 ; i --)
		ans = min(ans , solve(i));
	cout << ans;
	return(0);
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 4 ms 588 KB Output is correct
14 Correct 171 ms 856 KB Output is correct
15 Correct 32 ms 724 KB Output is correct
16 Correct 595 ms 848 KB Output is correct
17 Correct 1182 ms 904 KB Output is correct
18 Correct 1171 ms 908 KB Output is correct