Submission #350838

#	Time	Username	Problem	Language	Result	Execution time	Memory
350838		MHNaderi	Bosses (BOI16_bosses)	C++14	100 / 100	865 ms	1020 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin() , x.end()
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define random_init mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
const int maxn=1e4,INF=1e18;
int dis[maxn],mark[maxn],cntd[maxn];
vector<int> m[maxn];
inline int BFS(int u,int n){
    queue<int> q;
    q.push(u);
    mark[u]=1;
    dis[u]=1;
    cntd[dis[u]]=1;
    int mx=0;
//    cout<<"####"<<u<<"####"<<'\n';
    while(q.size()){
        u=q.front();
        for(int v : m[u]){
            if(!mark[v]){
                dis[v]=dis[u]+1;
                cntd[dis[v]]++;
                mark[v]=1;
                q.push(v);
            }
        }
        mx=dis[u];
        q.pop();
    }
    int ans=0,sum=0;
    for(int i=mx;i>0;i--){
        sum+=cntd[i];
        ans+=sum;
//        cout<<i<<" "<<cntd[i]<<'\n';
    }
    int cnt=0;
    for(int i=0;i<=n;i++){
        if(mark[i]) cnt++;
        dis[i]=cntd[i]=mark[i]=0;
    }
    if(cnt<n) return -1;
    return ans;
}
int mk[maxn];
void DFS(int u){
    mk[u]=1;
    for(int v : m[u]){
        if(!mk[v]) DFS(v);
    }
}
int32_t main(){
	ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
        int k; cin>>k;
        for(int j=0;j<k;j++){
            int x; cin>>x;
            m[x].pb(i);
        }
	}
    int ans=INF;
    for(int i=1;i<=n;i++){
        int x=BFS(i,n);
        if(x!=-1)
        ans=min(ans,x);
    }
    cout<<(ans==INF ? -1 : ans);
	return 0;
}

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