제출 #290049

#제출 시각아이디문제언어결과실행 시간메모리
290049MasterTasterBosses (BOI16_bosses)C++14
22 / 100
1 ms384 KiB
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"

vector<int> g[15], p[15];
int n, k[15], koga[15], trRess;
bool bio[15];
int ress;

int dfs(int u)
{
    bio[u]=true;
    //cout<<u<<endl;
    int suma=0;
    for (auto v:g[u])
    {
        if (!bio[v])
        {
            suma+=dfs(v);
        }
    }
    trRess+=suma+1;
    return (suma)+1;
}

void popravi()
{
    int koliko=0, root=-1;
    for (int i=1; i<=n; i++)
    {
        if (koga[i]==-1) { koliko++; root=i; }
    }

    if (koliko!=1) return;

    for (int i=1; i<=n; i++) { g[i].clear(); bio[i]=false; }
    for (int i=1; i<=n; i++) { if (i!=root) g[koga[i]].pb(i); }

    trRess=0;
    dfs(root);

    for (int i=1; i<=n; i++) if (!bio[i]) return;

    //for (int i=1; i<=n; i++) cout<<koga[i]<<" ";
    //cout<<endl<<trRess<<endl;
    ress=min(ress, trRess);
}

void uradi(int x, bool bio)
{
    if (x==n+1)
    {
        popravi();
        return;
    }

    if (!bio) { koga[x]=-1; uradi(x+1, true); }
    for (int i=0; i<k[x]; i++)
    {
        koga[x]=p[x][i];
        uradi(x+1, bio);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>k[i];
        for (int j=0; j<k[i]; j++)
        {
            int x; cin>>x;
            p[i].pb(x);
        }
    }

    ress=1010;
    uradi(1, 0);

    cout<<ress;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...