Решение задачи "Принцессы и принцы" с Codeforces

Без пояснения   Просмотров: 8


У короля Берляндии Поликарпа LXXXIV есть n дочерей. Чтобы показать свою власть соседним королевствам, он хочет выдать своих дочерей замуж за принцев этих королевств. По счастливой случайности других королевств так же n.

Поликарп LXXXIV занумеровал своих дочерей от 1 до n и королевства от 1 до n. Дальше для каждой дочери он собрал списки королевств, за принцев которых она хочет выйти замуж.

Поликарп LXXXIV — очень занятой правитель, поэтому он просто жадно находит пару своим дочерям одну за другой.

Для первой дочери он выбирает королевство с наименьшим номером из ее списка и выдает дочь за их принца. Для второй дочери он выбирает королевство с наименьшим номером из ее списка, принц которой еще не женат. Если нет неженатых принцев в списке, то дочь не выходит замуж ни за кого, а Поликарп LXXXIV переходит к следующей дочери. Процесс заканчивается после n-й дочери.

Например, пусть будет 4 дочери и королевства, списки дочерей: [2,3], [1,2], [3,4], [3], соответственно.
В данном случае дочь 1 выходит замуж за принца королевства 2, дочь 2 выходит замуж за принца королевства 1, дочь 3 выходит замуж за принца королевства 3, оставляя дочь 4 без возможности выйти замуж за кого-либо.

На самом деле, до начала всех женитьб у Поликарпа LXXXIV есть время убедить одну из своих дочерей, что за принца какого-либо королевства тоже можно выйти замуж. Фактически, это значит, что он может добавить ровно одно королевство в список ровно одной из своих дочерей. Обратите внимание, что данное королевство не должно содержаться в списке данной дочери.

Поликарп LXXXIV хочет увеличить количество женатых пар.

К сожалению, на что у него нет времени, так это на нахождение записи, которую стоит добавить. Если не существует способа увеличить количество женатых пар, то сообщите, что женитьбы уже оптимальны. Иначе найдите такую запись, после добавления которой итоговое количество женатых пар увеличится.

Если существует несколько способов добавить одну запись так, что количество женатых пар увеличится, то выведите любой из них.

Для вашего и нашего удобства мы просим вас ответить на t независимых наборов тестовых данных.

Код

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int t,n,k,x,y;
	scanf("%d",&t);
	for(;t--;){
		scanf("%d",&n);
		y=-1;
		bool p[n]{},v[n+1]{};
		for(int i=0;i<n;i++){
			scanf("%d",&k);
			for(int j=0;j<k;j++){
				scanf("%d",&x);
				if(v[x]||p[i])continue;
				p[i]=v[x]=1;
			}
			if(!p[i]&&y==-1)y=i;
		}
		if(y==-1)puts("OPTIMAL");
		else{
			puts("IMPROVE");
			for(int i=1;i<=n;i++)if(!v[i]){
				printf("%d %d\n",y+1,i);
				break;
			}
		}
	}
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться