oj.uz

Submission #567683

# Submission time Handle Problem Language Result Execution time Memory
567683 2022-05-24T04:00:48 Z Garguy22 Bosses (BOI16_bosses) C++17
0 / 100
 1 ms 468 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9 + 7;

vector<int> adj[5007], nex[5007];
bool vis[5007];
int val[5007];

void dfs(int u){
	int temp = 0;
	for(auto v : nex[u]){
		dfs(v);
		temp += val[v];
	}
	val[u] = temp + 1;
}

int main(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		int k;
		cin >> k;
		while(k--){
			int temp;
			cin >> temp;
			adj[temp].push_back(i);
		}
	}
	int ans = INF;
	for(int i = 1; i <= n; i++){
		vis[i] = 1;
		queue<int> q;
		q.push(i);
		while(!q.empty()){
			int u = q.front();
			q.pop();
			for(auto v : adj[u]){
				if(!vis[v]){
					nex[u].push_back(v);
					vis[v] = 1;
					q.push(v);
				}
			}
		}
		bool chk = 1;
		for(int j = 1; j <= n; j++){
			if(!vis[j]){
				chk = 0;
				break;
			}
		}
		if(chk){
			dfs(i);
			int sum = 0;
			for(int j = 1; j <= n; j++)
				sum += val[j];
			ans = min(ans, sum);
		}
	}
	cout << ans << endl;

	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 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 Incorrect 1 ms 468 KB Output isn't correct
3 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 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -