Submission #791136

#	Time	Username	Problem	Language	Result	Execution time	Memory
791136		shoryu386	Bosses (BOI16_bosses)	C++17	100 / 100	520 ms	596 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> adjList[n]; //who accepts this person
	for (int x = 0; x < n; x++){
		int num, temp;
		cin >> num;
		
		for (int y = 0; y < num; y++){
			cin >> temp;
			adjList[temp-1].push_back(x);
		}
	}
	
	//try every person as root, perform bfs style
	long long bestans = LONG_LONG_MAX;
	for (int x = 0; x < n; x++){
		int depths[n]; //also functions as visited
		memset(depths, -1, sizeof(depths));
		queue<pair<int, int>> bfs; 
		depths[x] = 1; //1 for root (a bit unconventional but who cares)
		
		bfs.push(make_pair(x, 1));
		
		while (!bfs.empty()){
			int front = bfs.front().first;
			int d = bfs.front().second;
			bfs.pop();
			for (int y : adjList[front]){
				if (depths[y] == -1){
					//don't touch already used nodes
					depths[y] = d+1;
					bfs.push(make_pair(y, d+1));
				}
			}
		}
		
		bool failed = false;
		long long ans = 0;
		for (int y = 0; y < n; y++){
			if (depths[y] == -1){ failed = true; break;}
			else ans += depths[y];
		}
		
		if (!failed) bestans = min(ans, bestans);
	}
	cout << bestans;
}

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