Submission #1121362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121362		heey	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	336 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> adj;
int res = 0;
int nfs(int v){
	if(adj[v].size() == 0) {
		res += 1;
		return 1;
	}

	int p = 0;
	for(int i : adj[v]){
		p += nfs(i);
	}
	p++;

	res += p;
	return p;
}

signed main(){
	//ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<vector<int>> a(n);
	for(int i = 0; i < n; i++){
		int k; cin >> k;
		a[i] = vector<int>(k);
		for(int j = 0; j < k; j++){
			cin >> a[i][j];
			a[i][j]--;
		}
	}
	vector<pair<vector<int>, int>> g(n);
	for(int i = 0; i < n; i++){
		g[i] = {vector<int>(), i};
		for(int j : a[i]){
			g[j].first.push_back(i);
		}
	}
	

	sort(g.begin(), g.end(), [&](const pair<vector<int>, int> &l, const pair<vector<int>, int> &r){ return l.first.size() < r.first.size();});
	reverse(g.begin(), g.end());
	
	vector<bool> mark(n, false);
	adj = vector<vector<int>>(n);
	for(int i = 0; i < n; i++){
		mark[g[i].second] = true;
		for(int j : g[i].first){
			if(!mark[j]) adj[g[i].second].push_back(j);
			mark[j] = true;
		}
	}

	
	nfs(g[0].second);
	cout << res << '\n';

	return 0;
}

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