제출 #1022541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022541		MrPavlito	Bosses (BOI16_bosses)	C++17	100 / 100	481 ms	916 KiB

bosses

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 5000+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n;
int mn = inf;

vector<vector<int>> graf(MAXN);

void bfs(int nod)
{
    queue<pii> q;
    q.push(mp(nod,1));
    vector<bool>visited(n+1, 0);
    int cnt = 0;
    int rez = 0;
    while(!q.empty())
    {
        pii tr = q.front();
        q.pop();
        if(visited[tr.fi])continue;
        visited[tr.fi] = 1;
        cnt++;
        rez+= tr.sc;
        for(auto x: graf[tr.fi])q.push(mp(x, tr.sc+1));
    }
    if(cnt == n)mn = min(mn, rez);
}

signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {
        cin >> n;
        for(int i=1; i<=n; i++)
        {
            int a;cin >> a;
            for(int j=0; j<a; j++)
            {
                int b;cin >> b;
                graf[b].pb(i);
            }
        }
        for(int i=1; i<=n; i++)
        {
            bfs(i);
        }
        cout << mn << endl;

    }
}

/*
1 4
2 1
2 3
2 4
3 1
3 2
4 3
*/

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