oj.uz

Submission #884334

# Submission time Handle Problem Language Result Execution time Memory
884334 2023-12-07T07:18:19 Z vjudge1 Bosses (BOI16_bosses) C++17
67 / 100
 1500 ms 3456 KB 
// in the name of God
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define fast() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ff first
#define ss second
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
#define mk make_pair
#define ppb pop_back
#define endl '\n'
#define pii pair<int, int>
#define sz(x) (int)x.size()
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O4")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7, maxn = 1e5 + 10, inf = 1e9 + 1, lg = 25, pp = 4447, modd = 1e9 + 9;

vector<vector<int>> g(maxn);
int n, ans = inf;

void bfs(int v){
	vector<int> dist(n, inf);
	map<int, int> t;
	dist[v] = 0;
	queue<int> q;
	q.push(v);
	while(q.size()){
		int u = q.front();
		q.pop();
		for(int v : g[u]){
			if(dist[v] > dist[u] + 1){
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
	}
	for(int i = 0; i < n; ++i){
		if(dist[i] == inf) return;
		t[dist[i]]++;
	}
	int x = 0, anss = 0;
	for(int i = n; i >= 0; --i){
		x += t[i];
		anss += x;
	}
	ans = min(ans, anss);
}
signed main(){
	fast();
	cin >> n;
	for(int i = 0; i < n; ++i){
		int t; cin >> t;
		for(int j = 0; j < t; ++j){
			int u; cin >> u;
			u--;
			g[u].pb(i);
		}
	}
	for(int i = 0; i < n; ++i){
		bfs(i);
	}
	cout << ans;
}
// Running from the daylight...

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2612 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 8 ms 2908 KB Output is correct
13 Correct 5 ms 2908 KB Output is correct
14 Correct 83 ms 3252 KB Output is correct
15 Correct 7 ms 3208 KB Output is correct
16 Correct 441 ms 3280 KB Output is correct
17 Execution timed out 1517 ms 3456 KB Time limit exceeded
18 Halted 0 ms 0 KB -