Submission #350545

#	Time	Username	Problem	Language	Result	Execution time	Memory
350545		saniyar_krmi	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	748 KiB

bosses

// YOU ONLY GOT ONE SHOT
#include <bits/stdc++.h>
#define put(x) cerr << #x << ": " << x << '\n'
#define line() cerr << "**************\n"
#define int long long 
#pragma GCC optimize ("Ofast")

//#define F first
//#define S second
//#define mul(x, y) (((x) * (y)) %mod)
//#define bit(i, j) (((i)>>(j)) &1)
//#define left(id) ((id<<1) + 1)
//#define right(id) ((id<<1) + 2)
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;

const int maxn = 5000 + 10;
const ll inf = 1e18 + 10;
int n;
vector <int> G[maxn], List[maxn], adj[maxn];
bool mark[maxn];
int sz[maxn];

ll dfs(int v, int par){
	ll res = 0;
	sz[v] = 1;
	for(int u: adj[v]){
		if(u == par)
			continue;
		res += dfs(u, v);
		sz[v] += sz[u];
	}
	res += sz[v];
	return res;
}

void bfs(int src){
	fill(mark, mark+maxn, 0);
	queue <int> q;
	q.push(src);
	mark[src] = 1;
	while(!q.empty()){
		int v = q.front();
		q.pop();
		for(int u: G[v]){
			if(mark[u])
				continue;
			mark[u] = 1;
			adj[v].push_back(u), adj[u].push_back(v);
			q.push(u);
		}
	}
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);

	cin >> n;
	int k;
	for(int i=1; i<=n; i++){
		cin >> k;
		List[i].resize(k);
		for(int j=0; j<k; j++){
			cin >> List[i][j];
			G[List[i][j]].push_back(i);
		}
	}

	ll ans = inf;
	for(int i=1; i<=n; i++){
		bfs(i);

		ans = min(ans, dfs(i, 0));

		for(int j=1; j<=n; j++)
			adj[j].clear();
		fill(sz, sz+maxn, 0);
	}

	cout << ans << '\n';
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33