Решение задачи Ехаб и неПутевые MEXы с Codeforces

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

Вам дано дерево, состоящее из n вершин. Вы хотите написать какие-то числа на ребрах дерева, чтобы выполнялись следующие условия:

Каждое написанное число является целым числом от 0 до n−2 включительно.
Все написанные числа различны.
Наибольшее значение среди MEX(u,v) среди всех пар вершин (u,v) минимально возможно.
Здесь MEX(u,v) обозначает наименьшее неотрицательное целое число, которое не записано ни на одном ребре уникального простого пути между вершинами u и v.

Код 

#include <bits/stdc++.h>

using namespace std;

int ans[100005];

int main() {
	memset(ans, -1, sizeof ans);
	int n;
	cin >>n;
	vector<int> v[n+1];
	
	for(int x, y, i = 1; i < n; i++) cin >>x >>y, v[x].push_back(i), v[y].push_back(i);

	for(int k = 3, i = 1; i <= n; i++) if(v[i].size() >= 3) {
		for(int j = 0; j < 3; j++) ans[v[i][j]] = j;
		for(int j = 1; j < n; j++) cout<<(ans[j] == -1 ? k++ : ans[j]) << "\n";
		exit(0);
	}
	
	for(int i = 0; i < n-1; i++) cout << i << "\n";
}

         

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



Комментарии

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


© 2020 HSECODES bminhojkhon03@gmail.com Карта сайта