oj.uz

Submission #858320

# Submission time Handle Problem Language Result Execution time Memory
858320 2023-10-08T06:08:27 Z 8pete8 Bosses (BOI16_bosses) C++14
100 / 100
 415 ms 832 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<list>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define p push
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=5005,mod=69,lg=42,root=80,inf=1e18;
vector<int>adj[mxn+10];
bitset<mxn+10>on;
int n,ans=inf;
void solve(int root){
    on.reset();
    queue<int>q;
    vector<int>val(n+1);
    int sum=1;
    val[root]=1;
    q.push(root);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        on[cur]=true;
        for(auto i:adj[cur]){
            if(on[i])continue;
            on[i]=true;
            val[i]=val[cur]+1;
            sum+=val[i];
            q.push(i);
        }
    }
    for(int i=1;i<=n;i++)if(!on[i])return;
    ans=min(ans,sum);
}
int32_t main(){
    fastio
    cin>>n;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        for(int j=0;j<a;j++){
            int v;cin>>v;
            adj[v].pb(i);
        }
    }
    for(int i=1;i<=n;i++)solve(i);
    cout<<ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 77 ms 728 KB Output is correct
15 Correct 4 ms 604 KB Output is correct
16 Correct 415 ms 832 KB Output is correct
17 Correct 410 ms 716 KB Output is correct
18 Correct 410 ms 820 KB Output is correct