/*
_____ _ _
/ ____| | | | |
| | __ _ __ __ _ ___ ___ _ _ _ __ ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
\_____|_| \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
__/ | |
|___/|_|
*/
#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
//#define f first
//#define s second
#define sz size
#define pob pop_back
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))
#define HEX 0x3f3f3f3f
using ll = long long;
const int INF = 5005;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};
int n;
vector<int> adj[INF];
vector<int> adj2[INF];
bool visited[INF];
int salary = 0;
bool visited2[INF];
int dfs(int node) {
int cnt = 1;
visited2[node] = true;
for (auto neighbor : adj2[node]) {
if (!visited2[neighbor]) {
cnt += dfs(neighbor);
}
}
salary += cnt;
return cnt;
}
int main()
{
std::ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
FOR(i, 1, n) {
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
adj[x].pb(i);
}
}
int ans = 1e9;
FOR(i, 1, 1) {
FOR(j, 1, n) adj2[i].clear();
mem(visited, false);
queue<int> q;
q.push(i);
visited[i] = true;
int num_visited = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
num_visited++;
for (auto neighbor : adj[node]) {
if (!visited[neighbor]) {
adj2[node].pb(neighbor);
visited[neighbor] = true;
q.push(neighbor);
}
}
}
if (num_visited == n) {
mem(visited2, false);
salary = 0;
dfs(i);
ans = min(ans, salary);
}
}
cout << ans << '\n';
return 0;
}
/*
* for each node, draw a direct edge from its
* accepted boss to the node
*
* fix each node as the root node
* bfs the ideal tree
* for each iteration, push the next visited
* neighbors into an adj list for the current node
*
* if all nodes are visited, this tree is valid
* use dfs and set each leaf to 1 and
* work your way up to the level 99 mafia boss
*/
//4
//1 4
//3 1 3 4
//2 1 2
//1 3
Compilation message
bosses.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
12 | #pragma gcc target ("avx2")
|
bosses.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
13 | #pragma gcc optimization ("O3")
|
bosses.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
14 | #pragma gcc optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
460 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
