oj.uz

Submission #952811

# Submission time Handle Problem Language Result Execution time Memory
952811 2024-03-25T00:25:45 Z sondos225 Bosses (BOI16_bosses) C++17
100 / 100
 423 ms 824 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;//find_by_order(ind);
//order_of_key()
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
#define vi vector<int>
signed main()
{
//    #ifndef LOCAL
//    freopen("lifeguards.in","r",stdin);
//    freopen("lifeguards.out","w", stdout);
//    #endif
    fast
    int n;
    cin>>n;
    vi a[n+1];
    forr(i,0,n)
    {
        int w;
        cin>>w;
        while(w--)
        {
            int x;
            cin>>x;
            a[x].pb(i+1);
        }
    }
        int ans=bigg;
        forr(i,1,n+1)
        {
            //big boss
        int depth[n+1]={ };
        queue <int> q;
        q.push(i);
        depth[i]=1;

        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            //out<<x<<endl;
            for(auto y:a[x])
            {
               // cout<<yes<<y<<' '<<depth[y]<<endl;
                if (depth[y]==0)
                {
                    depth[y]=depth[x]+1;
                    q.push(y);
                }
            }
        }
        int cur=0;
        forr(j,1,n+1)
            {
                //cout<<j<<' '<<depth[j]<<endl;
                int t=depth[j];
               if (t==0){ cur=bigg; break; }
               cur+=t;
            }
            ans=min(ans,cur);
        }
        cout<<ans;
    return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
45.0 / 45.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 388 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 352 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 0 ms 356 KB Output is correct
12 Correct 3 ms 608 KB Output is correct
13 Correct 3 ms 668 KB Output is correct
14 Correct 78 ms 720 KB Output is correct
15 Correct 4 ms 600 KB Output is correct
16 Correct 423 ms 824 KB Output is correct
17 Correct 403 ms 812 KB Output is correct
18 Correct 387 ms 804 KB Output is correct