Submission #438180

#	Time	Username	Problem	Language	Result	Execution time	Memory
438180		Urvuk3	Bosses (BOI16_bosses)	C++17	100 / 100	794 ms	708 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=5005,INF=1e10 ;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define endl "\n"
#define PRINT(x) cout<<#x<<'-'<<x<<endl

ll n, m, k, q, l, r, x, y, z, res=INF, tmp=0;
string s,t;
vector<int> adj[MAXN];
ll dist[MAXN];
bool visited[MAXN];

ll bfs(int x){
    queue<int> q;
    dist[x]=1;
    visited[x]=true;
    q.push(x);
    while(!q.empty()){
        int s=q.front(); q.pop();
        for(auto v:adj[s]){
            if(visited[v]) continue;
            visited[v]=true;
            dist[v]=dist[s]+1;
            q.push(v);
        }
    }
    ll sum=0;
    for(int i=1;i<=n;i++){
        sum+=dist[i];
    }
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            return INF;
        }
    }
    return sum;
}

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q;
        for(int j=0;j<q;j++){
            cin>>x;
            adj[x].push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        memset(visited,false,sizeof(visited));
        memset(dist,0,sizeof(dist));
        tmp=0;
        res=min(res,bfs(i));
    }
    cout<<res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 33 / 33