| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 290266 | MasterTaster | Bosses (BOI16_bosses) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 d[5010];
map<int, bool> bio;
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);
}
}
ll bfs(int s)
{
queue<int> q;
q.push(s);
d[s]=1;
bio[s]=true;
while (!q.empty())
{
int u=q.front();
q.pop();
for (auto v:g[u])
{
if (!bio[v])
{
d[v]=d[u]+1;
bio[v]=true;
q.push(v);
}
}
}
ll ret=0;
for (int i=1; i<=n; i++) ret+=d[i];
return ret;
}
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;
g[x].pb(i);
}
}
//ress=1010;
//uradi(1, 0);
ress=10000000000000010;
for (int i=1; i<=n; i++)
{
bio.clear();
ll trRess=bfs(i);
//cout<<trRess<<endl;
ress=min(ress, trRess);
}
cout<<ress;
}