Submission #1366106

#TimeUsernameProblemLanguageResultExecution timeMemory
1366106ivazivaBosses (BOI16_bosses)C++20
22 / 100
15 ms432 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 5001
#define int long long

int n;
vector<int> adj[MAXN];
vector<pair<int,int>> edges;
int parent[MAXN];
vector<int> graph[MAXN];
int dist[MAXN];
bool cycle=false;
int number=0;

void dfs(int node,int pret,int depth)
{
	if (cycle==true) return;
	dist[node]=depth;number++;
	for (int sled:graph[node])
	{
		if (sled==pret) continue;
		if (dist[sled]!=-1) {cycle=true;return;}
		dfs(sled,node,depth+1);
	}
}

int32_t main()
{
	cin>>n;
	for (int node=1;node<=n;node++)
	{
		int number;cin>>number;for (int pos=1;pos<=number;pos++) {int sled;cin>>sled;adj[node].push_back(sled);}
    }
    if (n<=10)
    {
		int answer=LLONG_MAX;
		for (int node=1;node<=n;node++)
		{
			for (int sled:adj[node]) edges.push_back({node,sled});
		}
		for (int maska=0;maska<(1<<(int)edges.size());maska++)
		{
			if (__builtin_popcount(maska)!=n-1) continue;
			for (int node=1;node<=n;node++) {parent[node]=-1;graph[node].clear();dist[node]=-1;}
			for (int bit=0;bit<(int)edges.size();bit++)
			{
				if (!(maska&(1<<bit))) continue;
				parent[edges[bit].first]=edges[bit].second;
			}
			bool valid=true;int root=-1;
			for (int node=1;node<=n;node++)
			{
				if (parent[node]==-1 and root==-1) root=node;
				else if (parent[node]==-1 and root!=-1) {valid=false;break;}
			}
			if (!valid) continue;
			for (int node=1;node<=n;node++)
			{
				if (parent[node]!=-1) {graph[node].push_back(parent[node]);graph[parent[node]].push_back(node);}
			}
			cycle=false;number=0;dfs(root,0,1);if (cycle or number!=n) continue;
			int solution=0;for (int node=1;node<=n;node++) solution+=dist[node];
			answer=min(answer,solution);
		}
		cout<<answer<<endl;return 0;
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...