Submission #297748

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
297748	2020-09-11T21:09:33 Z	eggag32	Bosses (BOI16_bosses)	C++17	100 / 100	1328 ms	888 KB

bosses

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int mxN = 5005;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int vis[mxN];
ll d[mxN];
int p1[mxN];
vi nxt[mxN];
ll ret = 1e18;
ll ans = 0LL;

void dfs(int v){
	if(ans >= ret) return;
	d[v] = 1;
	for(int u : nxt[v]) if(p1[u] == v){
		dfs(u);
		d[v] += d[u];
	}
	ans += d[v];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n;
	cin >> n;
	rep(i, n){
		int k;
		cin >> k;
		rep(j, k){
			int p;
			cin >> p;
			nxt[p - 1].pb(i);
		}
	}
	rep(i, n){
		memset(vis, 0, sizeof(vis));
		queue<int> q;
		q.push(i);
		p1[i] = -1;
		vis[i] = 1;
		int cnt = 1;
		while(!q.empty()){
			int cur = q.front();
			q.pop();
			for(int u : nxt[cur]) if(!vis[u]){
				p1[u] = cur;
				q.push(u);
				vis[u] = 1;
				cnt++;
			}
		}
		if(cnt == n){
			ans = 0LL;
			dfs(i);
			ret = min(ret, ans);
		}
	}
	cout << ret << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Subtask #1

22.0 / 22.0

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

Subtask #2

45.0 / 45.0

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

Subtask #3

33.0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	512 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	1 ms	512 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	512 KB	Output is correct
7	Correct	1 ms	640 KB	Output is correct
8	Correct	1 ms	512 KB	Output is correct
9	Correct	1 ms	512 KB	Output is correct
10	Correct	1 ms	640 KB	Output is correct
11	Correct	1 ms	512 KB	Output is correct
12	Correct	8 ms	512 KB	Output is correct
13	Correct	7 ms	512 KB	Output is correct
14	Correct	141 ms	888 KB	Output is correct
15	Correct	7 ms	640 KB	Output is correct
16	Correct	606 ms	640 KB	Output is correct
17	Correct	1328 ms	760 KB	Output is correct
18	Correct	1278 ms	768 KB	Output is correct