제출 #74004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74004		claudy	Bosses (BOI16_bosses)	C++14	100 / 100	965 ms	4876 KiB

bosses

# pragma GCC optimize("O3")
# include <bits/stdc++.h>
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

int n,k,x;
vector<int>vec[1 << 17];
int viz[1 << 17];

int f(int nod)
{
    queue<pair<int,int>>q;
    memset(viz,0,sizeof(viz));
    q.push(mp(nod,1));
    int cnt = 0;
    int x = 0;
    while(!q.empty())
    {
        int v = q.front().first;
        int cst = q.front().second;
        q.pop();
        if(viz[v]) continue;
        viz[v] = 1;
        x += cst;
        cnt++;
        for(auto it : vec[v])
        {
            if(!viz[it]){
                q.push(mp(it,cst + 1));
            }    
        }
    }
    if(cnt == n)
    return x;
    else return 1e9;
}

int32_t main(){_
    //freopen("input","r",stdin);
    cin >> n;
    for(int i = 1;i <= n;i++)
    {
        cin >> k;
        while(k--)
        {
            cin >> x;
            vec[x].pb(i);
        }
    }
    int ans = 1e9;
    for(int i = 1;i <= n;i++)
    {
        ans = min(ans,f(i));
    }
    rc(ans);
}

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