oj.uz

Submission #839197

# Submission time Handle Problem Language Result Execution time Memory
839197 2023-08-29T03:47:55 Z vjudge1 Bosses (BOI16_bosses) C++17
0 / 100
 1 ms 724 KB 
#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],q[mxn];

ll n,k = 0;

ll cnt[mxn],t[mxn];

bool used[mxn];

ll dfs(ll x){
    used[x] = true;
    deque <pair<ll,ll> > q;
    q.push_back(m_p(x,1));
    ll ans = 0;
    while(!q.empty()){
        k ++;
        ans += q[0].second;
        ll f = q[0].first;
        for(auto i : v[f]){
            if(used[i] == false){
                used[i] = true;
                q.push_back(m_p(i,q[0].second + 1));
            }
        }
        q.pop_front();
    }
    if(k != n) return inf;
    else return ans;
}

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 mn = inf;
    FOR(i,1,n + 1){
        memset(used,false,sizeof(used));
        ll p = dfs(i);
        mn = min(mn,p);
    }
    cout << mn;
}
/*
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

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
      |

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Halted 0 ms 0 KB -