/**
* \author KienNguyen246
* \date 22/12/2020
*/
///😭😢😞☹🙁😐🙂☺😊😁😀😆😂🤣
///----------------🤔🤔🤔 -----------------///
/**< 🤣🤣🤣 */
#include <bits/stdc++.h>
///TLE (in case of emergency)
#define TLE 0
#if TLE
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("unroll-loops")
#endif // TLE
#define NOT_INTERACTIVE 1
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
//const int maxn = 105;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int infi = (2e9 + 69);
const ll infy = (2e16 + 69);
const int base = 311;
const ll MM = 7ll * mod * mod;
const int addition = 1e5;
const db eps = 1e-8;
const string numd[10] = {"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"};
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const double pi = 3.14159265358980;
const string P1 = "Ashish";
const string P2 = "Utkarsh";
const string spmcode = "My power does not end. Ask for aid and you will receive it.\n";
template <typename Num> void maximize(Num &x, Num y) {x = mx(x, y);}
template <typename Num> void minimize(Num &x, Num y) {x = min(x, y);}
void exit_with_runtime() {db x = 1.0 * clock() / CLOCKS_PER_SEC; cerr << "\n\n---------------------\nTime elapsed: " << x << " s.\n\n"; exit(0);}
void decorate() {cerr << "KienNguyen246\n"; chrono:: system_clock::time_point today = chrono::system_clock::now(); time_t tt = chrono::system_clock::to_time_t(today); cerr << ctime(&tt); cerr << "\nProcessing...\n\n";}
///Multiple tests?
#define MUL_TEST 0
/**< 🤣🤣🤣 */
//bool Palin(string s) {string r = s; reverse(whole(r)); return (r == s);}
/* 🙃🙃🙃 */
int n, mk[25], in[25], tr[maxn];
long long res, f[25];
vector <pii> a[25];
vector <pii> e;
void DFS(int u)
{
for (auto p : a[u])
{
int v = p.first;
int id = p.second;
if (!mk[id] || tr[v]) continue;
tr[v] = u;
DFS(v);
f[u] += f[v];
}
}
void Calc(int state)
{
if (__builtin_popcount(state) != n - 1) return;
memset(mk, 0, sizeof(mk));
memset(tr, 0, sizeof(tr));
memset(in, 0, sizeof(in));
fill(f + 1, f + n + 1, 1);
for (int i = 0; i < e.size(); i ++) mk[i] = (state >> i) & 1;
for (int i = 0; i < e.size(); i ++)
if (mk[i]) in[e[i].second] ++;
int root = 0;
for (int i = 1; i <= n; i ++)
if (in[i] == 0)
{
if (!root) root = i;
else return;
}
tr[root] = -1;
if (root) DFS(root);
for (int i = 1; i <= n; i ++)
if (tr[i] == 0) return;
res = min(res, accumulate(f + 1, f + n + 1, 0ll));
}
//My power does not end. Ask for aid and you will receive it.
void Main_Process()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
int cnt;
cin >> cnt;
for (int u, j = 1; j <= cnt; j ++)
{
cin >> u;
a[u].push_back({i, e.size()});
e.push_back({u, i});
}
}
res = 1e18 + 69;
for (int i = 0; i < (1 << e.size()); i ++)
Calc(i);
cout << res;
}
/**< 😂😂😂 */
int main()
{
/**< Main preprocessing begin */
ios_base::sync_with_stdio(0);
#if NOT_INTERACTIVE
// cin.tie(0); cout.tie(0);
decorate();
#endif
#ifndef ONLINE_JUDGE
freopen(".inp", "r", stdin);
// freopen(".out", "w", stdout);
#endif
/**< Main preprocessing end */
/*😍😍😍*/
int test = 1;
cerr << spmcode << "\n";
#if MUL_TEST
cin >> test;
#endif
while (test --) Main_Process();
exit_with_runtime();
}
/**< 😂😂😂 */
///😂😂😂😂😂😂😂😂🌚🔥😂😂😂😂🌚🔥😂😂🔥😂😂😂🔥😂😂😂🔥😂💯💯💯💯💩🐸🔥😂🔥😂🔥💩🔥🔥😂🌚💯🐸💯💩🐸🔥🔥💞🔥💩💩💩💞😂😂😂😂😂😂😂💞💞😂😂😂💞🔥🔥💞💯💩💞💯💞😂😂😂💞💩💩💩💩💩💩💞💩💩💩💩💩💩💩💩💞🔥🔥😂💞🔥😂😂💞
Compilation message
bosses.cpp: In function 'void Calc(int)':
bosses.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for (int i = 0; i < e.size(); i ++) mk[i] = (state >> i) & 1;
| ~~^~~~~~~~~~
bosses.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < e.size(); i ++)
| ~~^~~~~~~~~~
bosses.cpp: In function 'int main()':
bosses.cpp:135:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
135 | freopen(".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
