Submission #337878

#	Time	Username	Problem	Language	Result	Execution time	Memory
337878		kiennguyen246	Bosses (BOI16_bosses)	C++14	0 / 100	2 ms	364 KiB

bosses

/**
 * \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 (stderr)

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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33