oj.uz

Submission #453690

# Submission time Handle Problem Language Result Execution time Memory
453690 2021-08-04T15:12:45 Z Blobo2_Blobo2 Bosses (BOI16_bosses) C++14
67 / 100
 1500 ms 672 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++){
        priority_queue<pair<int,int> >q;
        bool vis[n];
        memset(vis,0,sizeof vis);
        q.push({0,i});
        int level[n];
        memset(level,0,sizeof level);
        vis[i]=1;
        level[0]++;
        int cnt=1;
        while(q.size()){
            pair<int,int> u=q.top();
            q.pop();
            for(auto v:adj[u.second]){
                if(!vis[v]){
                    level[(-u.first)+1]++;
                    q.push({u.first-1,v});
                    vis[v]=1;
                    cnt++;
                }
            }
            if(cnt==n)break;
        }
        if(cnt!=n)continue;
        int c=0;
        for(int i=n-2;i>=0;i--)
            level[i]+=level[i+1];
        for(int i=n-1;i>=0;i--)
            c+=level[i];
        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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 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 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 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
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 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 332 KB Output is correct
13 Correct 2 ms 460 KB Output is correct
14 Correct 269 ms 540 KB Output is correct
15 Correct 16 ms 588 KB Output is correct
16 Execution timed out 1589 ms 672 KB Time limit exceeded
17 Halted 0 ms 0 KB -