Submission #337869

#	Time	Username	Problem	Language	Result	Execution time	Memory
337869		KazamaHoang	Bosses (BOI16_bosses)	C++14	22 / 100	92 ms	620 KiB

bosses

/* -> Written by <-
   -----------
  K_A_Z_A_M_A
  ___________
      _    |
  |   (^_^)   |
  |  /( | )\  |
  |____|_|____|
    H O A N G
*/

#include <bits/stdc++.h>

#define Task            ""
#define F               first
#define S               second
#define pb              push_back
#define bit(x, i)       ((x >> (i)) & 1)
#define inf             1e9 + 7
#define INF             1e18 + 7
#define ll              long long
#define pii             pair <int, int>
#define debug(x)        cerr << #x << " is " << x << "\n";

using namespace std;

const int MOD = 1e9 + 7;
const int maxn = 5005;

int n, m = 0;
vector <int> ke[maxn];
pair <int, int> e[maxn];
int In[maxn];
int ans = 0;
int res = inf;
int d[maxn];
bool dd[maxn];

void dfs(int u){
    d[u] = 1;
    dd[u] = 1;
    for (auto v : ke[u]){
        if (dd[v]){
            continue;
        }
        dfs(v);
        d[u] += d[v];
    }
    ans += d[u];
}

void Cal(int mask){
    for (int i = 1; i <= n; ++ i) ke[i].clear(), In[i] = 0, dd[i] = 0, d[i] = 0;
    int cnt = 0;
    for (int i = 0; i < m; ++ i)
        if (bit(mask, i)){
            int u = e[i+1].F;
            int v = e[i+1].S;
            ke[u].pb(v);
            ++ cnt;
            ++ In[v];
            if (In[v] >= 2){
                return;
            }
        }
    if (cnt != n - 1) return;
    ans = 0;
    for (int i = 1; i <= n; ++ i)
        if (In[i] == 0) dfs(i);
    for (int i = 1; i <= n; ++ i)
        if (d[i] == 0) return;
    res = min(res, ans);
}

void Solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i){
        int x; cin >> x;
        for (int j = 1; j <= x; ++ j){
            int y; cin >> y;
            e[++m] = {y, i};
        }
    }
    for (int mask = 0; mask < (1 << m); ++ mask)
        Cal(mask);
    cout << res;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    if(fopen(Task".inp", "r")){
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
    int test_case = 1;
    // cin >> test_case;
    while (test_case --){
        Solve();
    }

    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   92 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bosses.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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