Submission #525414

#	Time	Username	Problem	Language	Result	Execution time	Memory
525414		fuad27	Bosses (BOI16_bosses)	C++17	100 / 100	675 ms	656 KiB

bosses

/*
 * Created: 2022 Feb 11 06:49:59 PM
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll INF = 1e18;

#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define rep(i, a, b) for(int i = a;i<b;i++)
#define ss second
#define ff first

template<typename T>
auto operator<<(ostream &os, T&v)->decltype(v.begin(), os){
	os << "[";
	int f = 0;
	for(auto i:v) {
		if(f++)os << ", ";
		os << i;
	}
	os << "]";
	return os;
}
template<typename F, typename S>
ostream& operator<<(ostream &os, pair<F, S> const &p) {
	return os << "(" << p.first << ", " << p.second << ")";	
}
void debug(){}
template<typename T, typename... V>
void debug(T t, V... v) {
	cerr << t;
	if(sizeof...(v)) {
		cerr << ", "; debug(v...);
	}
}
#ifdef LOCAL
#define dbg(x...) cerr << "[" << #x << "]: " << "["; debug(x); cerr << "]\n";
#else
#define dbg(x...)
#endif


struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};


void precompute() {

}



vector<int> g[5010];
void solve() {
	int n;
	cin >> n;
	int visited[n+1];
	for(int i = 0;i<n;i++)visited[i]=0;
	rep(i, 1, n+1) {
		int k, d;
		cin >> k;
		rep(j, 0, k) {
			cin >> d;
			g[d].push_back(i);
		}
	}
	long long ans = INF;
	rep(root, 1, n+1) {
		rep(i, 0, n+1)visited[i] = 0;
		queue<int> que;
		que.push(root);
		visited[root] = 1;
		long long calc = 0;
		while(!que.empty()) {
			int at = que.front();
			que.pop();
			for(int to:g[at]) {
				if(!visited[to]) {
					que.push(to);
					visited[to] = visited[at]+1;
				}
			}
		}
		rep(i,1,n+1) {
			if(!visited[i]) {
				calc = INF;
				break;
			}
			calc+=visited[i];
		}
		ans = min(ans, calc);
	}
	cout << ans << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	precompute();
	int t = 1;
	// cin >> t;
	while(t--) {
		solve(); }
	cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

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