oj.uz

Submission #569141

# Submission time Handle Problem Language Result Execution time Memory
569141 2022-05-26T19:14:41 Z beaconmc Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 536 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)

using namespace std;
ll n;
vector<vector<ll>> bosses;
vector<ll> edges[5001];
vector<ll> newedges[5001];
ll sum = 0;


int dfs(ll a){
	ll sus = 1;
	for (auto&i : newedges[a]){
		sus += dfs(i);
	}
	sum += sus;
	return sus;
}

ll solve(ll a){
	FOR(i,0,5001){
		edges[i] = {};
		newedges[i] = {};
	}
	FOR(i,0,n){
		for (auto&j : bosses[i]){
			edges[j].push_back(i+1);
		}
	}
	vector<bool> visited(n+1);

	queue<ll> q;
	q.push(a);
	visited[a] = 1;

	while (q.size()){
		ll node = q.front();
		q.pop();
		for (auto&i : edges[node]){
			if (!visited[i]){
				q.push(i);
				visited[i] = 1;
				newedges[node].push_back(i);
			}
		}
	}
	sum = 0;
	dfs(a);
	return sum;
}



int main(){
	cin >> n;

	FOR(i,0,n){
		ll temp; cin >> temp;
		vector<ll> templis(temp);
		FOR(i,0,temp) cin >> templis[i];
		bosses.push_back(templis);
	}
	ll mini = 1000000000;
	FOR(i,1,n+1){
		mini = min(mini, solve(i));
	}
	cout << mini;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -