Submission #289939

#	Time	Username	Problem	Language	Result	Execution time	Memory
289939		BeanZ	Bosses (BOI16_bosses)	C++14	100 / 100	1217 ms	900 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 5e5 + 5;
ll res;
ll vis[5005], cnt[5005];
vector<ll> node[5005];
void bfs(ll u){
        memset(vis, 0, sizeof(vis));
        memset(cnt, 0, sizeof(cnt));
        queue<ll> q;
        stack<pair<ll, ll>> s;
        s.push({u, 0});
        q.push(u);
        vis[u] = 1;
        while (q.size()){
                ll x = q.front();
                q.pop();
                for (auto j : node[x]){
                        if (vis[j]) continue;
                        vis[j] = 1;
                        q.push(j);
                        s.push({j, x});
                }
        }
        while (s.size()){
                cnt[s.top().first]++;
                res = res + cnt[s.top().first];
                cnt[s.top().second] += cnt[s.top().first];
                s.pop();
        }
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("simplify.in", "r")){
                freopen("simplify.in", "r", stdin);
                freopen("simplify.out", "w", stdout);
        }
        ll n;
        cin >> n;
        for (int i = 1; i <= n; i++){
                ll k;
                cin >> k;
                for (int j = 1; j <= k; j++){
                        ll u;
                        cin >> u;
                        node[u].push_back(i);
                }
        }
        ll ans = 1e18;
        for (int i = 1; i <= n; i++){
                res = 0;
                bfs(i);
                bool flag = true;
                for (int j = 1; j <= n; j++){
                        if (vis[j] == 0) flag = false;
                }
                if (flag) ans = min(ans, res);
        }
        cout << ans;
}
/*
*/

Compilation message (stderr)

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

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