Submission #1309772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309772		freedommo33	Bosses (BOI16_bosses)	C++20	22 / 100	88 ms	5200 KiB

bosses

#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define mp(a, b) make_pair(a, b)
using namespace std;

template <typename H, typename T>
ostream& operator<<(ostream& os, pair<H, T> p){
	return os << "("<<p.st<<","<<p.nd<<")";
}
template <typename H>
ostream& operator<<(ostream& os, vector<H> v){
	os << "{";
	for(int i=0; i<sz(v); i++){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

void debug() { cerr<<"\n"; }
template <typename H, typename... T>
void debug(H h, T... t) { cerr<<h; if(sizeof...(t)) cerr<<" "; debug(t...); }
#define deb(x...) cerr<<__LINE__<<":"<<#x<<" -> "; debug(x);

typedef long long ll;

constexpr int M = 2e5+7, INF = 1e9+7, mod = 1e9+7, base = 1<<18;

vector<vector<int>> g(M);
vector<pair<int, int>> przo;
int par[M];
int wyplata[M];

void dfs(int v, int p){
	wyplata[v] = 1;
	for(auto i:g[v]) if(i != p){
		dfs(i, v);
		wyplata[v] += wyplata[i];
	} 
}

void solve(){
	int n;
	cin>>n;
	for(int i=1; i<=n; i++){
		int a;
		cin>>a;
		for(int j=1; j<=a; j++){
			int b;
			cin>>b;
			przo.pb({i, b});
		}
	}
	int wynik = INF;
	//for(auto i:przo) cout<<i<<endl;
	
	for(int i=0; i<(1<<(sz(przo))); i++){
		//for(int j=1; j<=sz(przo); j++){
		//	if(i & (1<<(j-1))) cout<<1;
		//	else		   cout<<0;
		//}
		//cout<<" -> ";
		for(int j=1; j<=n; j++) par[j] = 0;
		for(int j=1; j<=sz(przo); j++){
			if(i & (1<<(j-1))) par[ przo[j-1].first ] = przo[j-1].second;
		}
		int ile0 = 0;
		int korz = 0;
		for(int j=1; j<=n; j++) if(par[j] == 0) ile0++, korz = j;
		if(ile0 > 1) continue;
		
		for(int j=1; j<=n; j++) g[j].clear();
		
		for(int j=1; j<=n; j++) if(j != korz){
			g[par[j]].pb(j);
			g[j].pb(par[j]);
		}
		int kraw = 0;
		bool czy = 0;
		for(int j=1; j<=n; j++){
			if(sz(g[j]) == 0){
				czy = 1;
				break;
			} 
			kraw += sz(g[j]);
		}
		if(czy == 1) continue;
		if(kraw != 2*n-2) continue;
		for(int j=1; j<=n; j++) wyplata[j] = 0;
		int aktWyn = 0;
		dfs(korz, 0);
		//cout<<endl;
		//for(int j=1; j<=n; j++){
		//	cout<<j<<": ";
		//	for(auto k:g[j]) cout<<k<<" ";
		//	cout<<endl;
		//}
		//cout<<endl;
		//for(int j=1; j<=n; j++) cout<<wyplata[j]<<" ";
		//cout<<endl;
		czy = 0;
		for(int j=1; j<=n; j++) if(wyplata[j] == 0){
			czy = 1;
			break;
		}
		if(czy) continue;
		for(int j=1; j<=n; j++) aktWyn += wyplata[j];
		//cout<<aktWyn<<endl;
		wynik = min(wynik, aktWyn);
	}
	cout<<wynik<<endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

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