Submission #838898

#	Time	Username	Problem	Language	Result	Execution time	Memory
838898		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	596 KiB

bosses

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma optimization_level 3
 
// Defines
 
#define pb push_back // kak push_back 5
#define endl '\n'
#define FOR(i,start,end) for(int i = start;i < end;i ++)
#define REV(i,start,end) for(int i = start;i >= end;i --)
#define precal(x) fixed << setprecision(x)
#define F first
#define S second
#define sz(x) (ll)x.size()
#define all(x) (x).begin(),(x).end()
#define m_p make_pair
#define mt make_tuple
#define str to_string

// #ifndef ONLINE_JUDGE
//     #define cerr if(false) cerr
// #endif
 
const ll mxn = 1e4;
// const ll k = 1000;
// const ll org = 10000;
const ll inf = 1e9 + 7;
// const ll mod = 998244353;

vector <ll> v[mxn];

ll n,k = 0;

ll cnt[mxn],t[mxn];

bool used[mxn];

void dfs(ll x,ll p = n){
    used[x] = true;
    if(t[x] == 0){
        t[x] = p;
        cnt[p] ++,k ++;
    }
    else{
        cnt[t[x]] --,t[x] = p,cnt[p] ++;
    }
    for(auto i : v[x]){
        if(t[i] == 0 && used[i] == false || p - 1 > t[i] && used[i] == false) dfs(i,p - 1);
    }
    used[x] = false;
}

int main(){
    // freopen("sparse.in","r",stdin);
    // freopen("sparse.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll tt = 1;
    // cin >> tt; 
    while(tt --){
        cin >> n;
        FOR(i,1,n + 1){
            ll t;
            cin >> t;
            while(t --){
                ll x;
                cin >> x;
                v[x].pb(i);
            }
        }
        ll ans = inf;
        FOR(i,1,n + 1){
            k = 0;
            memset(cnt,0,sizeof(cnt));
            memset(t,0,sizeof(t));
            dfs(i);
            if(k != n) continue;
            ll sum = 0,mnval = -1;
            for(int j = 1;j <= n;j ++){
                if(cnt[j] > 0 && mnval == -1) mnval = j;
                sum += cnt[j] * (j - mnval + 1);
            }
            ans = min(ans,sum);
            // cout << i << " " << ans << endl;
        }
        cout << ans;
    }
}
/*
5
4 2 3 4 5
4 1 3 4 5
4 1 2 4 5
4 1 2 3 5
4 1 2 3 4
*/

Compilation message (stderr)

bosses.cpp:9: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("O3")
      | 
bosses.cpp:10: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("unroll-loops")
      | 
bosses.cpp:11: warning: ignoring '#pragma optimization_level ' [-Wunknown-pragmas]
   11 | #pragma optimization_level 3
      | 
bosses.cpp: In function 'void dfs(ll, ll)':
bosses.cpp:56:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   56 |         if(t[i] == 0 && used[i] == false || p - 1 > t[i] && used[i] == false) dfs(i,p - 1);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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