oj.uz

Submission #453689

# Submission time Handle Problem Language Result Execution time Memory
453689 2021-08-04T15:11:44 Z Blobo2_Blobo2 Bosses (BOI16_bosses) C++14
100 / 100
 765 ms 612 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);

const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}

signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    int n=nxt();
    vector<int>adj[n+1];
    for(int i=0;i<n;i++){
        int x=nxt();
        for(int j=0;j<x;j++){
            int node = nxt()-1;
            adj[node].push_back(i);
        }
    }
    int mn=1e18;
    for(int i=0;i<n;i++){
        queue<pair<int,int> >q;
        bool vis[n];
        memset(vis,0,sizeof vis);
        q.push({1,i});
        vis[i]=1;
        int cnt=1,c=1;
        while(q.size()){
            pair<int,int> u=q.front();
            q.pop();
            for(auto v:adj[u.second]){
                if(!vis[v]){
                    q.push({u.first+1,v});
                    vis[v]=1;
                    cnt++;
                    c+=u.first+1;
                }
            }
            if(cnt==n)break;
        }
        if(cnt!=n)continue;
        mn=min(mn,c);
    }
    cout<<mn;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 3 ms 440 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 188 ms 460 KB Output is correct
15 Correct 4 ms 460 KB Output is correct
16 Correct 625 ms 612 KB Output is correct
17 Correct 765 ms 588 KB Output is correct
18 Correct 751 ms 588 KB Output is correct