oj.uz

Submission #584991

# Submission time Handle Problem Language Result Execution time Memory
584991 2022-06-28T08:16:50 Z ktkerem Bosses (BOI16_bosses) C++17
100 / 100
 762 ms 832 KB 
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#include <cstdlib>
/*#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 vll;
typedef unsigned __int128 uvll;
ll _i=0;
#define ffn(x) _i=x
#define llll std::pair<ll , ll>
#define stitr set<ll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e18 + 7; 
const ll ous = 5007;
const ll dx[4] = {1 , 0 , 0 , -1} , dy[4] = {0,1,-1,0};
std::vector<ll> adj[ous];
ll s = 0 , n;
ll vis[ous];
ll bfstest(ll x){
    memset(vis , 0 , sizeof(vis));
    s = 0;
    ll sum = 0;
    std::queue<llll> qu;
    qu.push({x , 1});
    vis[x] = 1;
    while(!qu.empty()){
        llll a = qu.front();
        //std::cout << a.fi << " " << a.sec << "\n";
        qu.pop();
        sum+=a.sec;
        s++;
        for(auto j:adj[a.fi]){
            if(vis[j] == 0){
                vis[j] = 1;
                qu.push({j , a.sec + 1});
            }
        }
    }
    if(s == n){
        return sum;
    }
    return -1;
}
void solve(){
    std::cin >> n;
    for(ll i = 1;n>=i;i++){
        ll k;std::cin >> k;
        fora(j , k){
            ll x;std::cin >> x;
            adj[x].pb(i);
        }
    }
    ll rt = limit;
    fora(i , n){
        ll s = bfstest(i + 1);
        rt = std::min(rt , (s == -1 ? limit :s));
        //std::cout << s << " " << i+1 << "\n";
    }
    if(rt == limit){
        rt = -1;
    }
    std::cout << rt << "\n";
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0; 
}

Compilation message

bosses.cpp:13:1: warning: "/*" within comment [-Wcomment]
   13 | /**/
      |  
bosses.cpp: In function 'int main()':
bosses.cpp:86:8: warning: unused variable 'o' [-Wunused-variable]
   86 |     ll o = 1;
      |        ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 436 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 4 ms 596 KB Output is correct
13 Correct 4 ms 684 KB Output is correct
14 Correct 198 ms 596 KB Output is correct
15 Correct 9 ms 596 KB Output is correct
16 Correct 609 ms 832 KB Output is correct
17 Correct 762 ms 684 KB Output is correct
18 Correct 759 ms 688 KB Output is correct