oj.uz

Submission #525414

# Submission time Handle Problem Language Result Execution time Memory
525414 2022-02-11T15:07:48 Z fuad27 Bosses (BOI16_bosses) C++17
100 / 100
 675 ms 656 KB 
/*
 * 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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 428 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 428 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 432 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 428 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 432 KB Output is correct
12 Correct 4 ms 440 KB Output is correct
13 Correct 3 ms 460 KB Output is correct
14 Correct 122 ms 548 KB Output is correct
15 Correct 5 ms 452 KB Output is correct
16 Correct 500 ms 640 KB Output is correct
17 Correct 675 ms 656 KB Output is correct
18 Correct 662 ms 648 KB Output is correct