제출 #1275861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275861		sadraallami	Bosses (BOI16_bosses)	C++20	100 / 100	451 ms	808 KiB

bosses

//وَمَكَروا وَمَكَرَ اللَّهُ ۖ وَاللَّهُ خَيرُ الماكِرينَ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> mat;
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fast (ios_base::sync_with_stdio(false), cin.tie(NULL));
#define print(n) for(ll i:n){std::cout << i << ' ';}std::cout << endl;
ll pw(ll a,ll b,ll md=1e9+3){ll res=1;b=max(b,0ll);while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res%md);}
const ll maxn=2e5+10;
const ll mod=1e9+7;
const ll sq=500;
const ll lg=30;
const ll inf=1e18;
int vis[maxn];
vector<ll> adj[maxn];
ll n,upd=0,cnt=0,dis[maxn],ans=inf;
void bfs(ll s){
    queue<ll> q;
    q.push(s);
    dis[s]=1;
    upd=1;
    vis[s]=1;
    cnt=0;
    while(q.size()){
        ll v=q.front();
        q.pop();
        //cout<< "* " << v << endl;
        cnt++;
        for(ll u:adj[v]){
            if(vis[u]==0){
                dis[u]=dis[v]+1;
                upd+=dis[u];
                vis[u]=1;
                q.push(u);
            }
        }
    }
    if(cnt<n)upd=inf;
}
int main(){
    fast;
    cin>>n;
    for(ll i=1;i<=n;i++){
        ll k;cin>>k;
        for(ll j=0;j<k;j++){
            ll x;cin>>x;
            adj[x].pb(i);
        }
    }
    for(ll i=1;i<=n;i++){
        bfs(i);
        //cout<< i << " --> " << upd << endl;
        fill(vis,vis+n+1,0);
        ans=min(ans,upd);
    }
    cout<< ans << endl;
}

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