4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс, Актобе

Задача A. Занимательная игра

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Недавно Айдос изучая культуру древних народов горных местностей, обнаружил одну очень занимательную игру. Как верили создатели этой игры, она играла очень важную роль в культуре и помогала развивать дедуктивное мышление людей всех возрастов. Айдос проникся интересностью игры и решил перевести ее на современный лад. Вот, что у него получилось. Изначально вам дается неориентированный граф с $n$ вершинами и $m$ ребрами. У каждой вершины $v$ есть значение $a_v$. Предлагается произвести над этим графом $q$ операций. Операции могут быть четырех типов:

1. Добавить ребро между существующими вершинами
2. Удалить существующее ребро из графа
3. Изменить значение одной вершины
4. Среди соседей заданной вершины найти $k$-ю по значению вершину.

Замечание. В графе могут быть кратные ребра и не гарантируется, что граф связный.

Формат входного файла

Первая строка входных данных содержит три целых чисел $n, m, q$ через пробел — количество вершин, ребер и операций $(1 <= n, m, q <= 2 \cdot 10^5)$. Вторая строка содержит $n$ целых чисел $a_1, a_2, ..., a_n$ через пробел — значения вершин $(1 <= a_i <= 10^9)$. Следующие $m$ строк содержат описания ребер графа, по два целых числа $u, v$ в каждой строке — неориентированное ребро между вершинами $u$ и $v$ $(1 <= u, v <= n)$. В каждой из следующих $q$ строк содержатся описания запросов. Каждое описание соответствует одному из следующих видов:

• 1 u v — добавить ребро между вершинами $u$ и $v$.
• 2 u v — удалить ребро между вершинами $u$ и $v$. Если их несколько, то удаляется только одно ребро.
• 3 u x — поменять значение вершины $u$ на $x$.
• 4 u k — выведите номер вершины по следующему правилу: отсортируйте соседние вершины $u$ сначала по значению вершин, затем по номеру (оба параметра — по неубыванию). Из отсортированного списка выведите $k$-ю вершину $(1 <= u, v <= 2 \cdot 10^5, 1 <= x <= 10^9)$.

Формат выходного файла

На каждый запрос типа 4 выведите в новой строке номер вершины согласно требованиям в запросе.

Система оценки

Данная задача содержит шесть подзадач:

1. $1 <= n, q <= 100$. Оценивается в 6 баллов.
2. $1 <= n, q <= 10000$, также в этой подзадаче нет второго типа запроса. Оценивается в 7 баллов.
3. $1 <= n, q <= 50000$. Оценивается в 22 баллов.
4. $1 <= n, q <= 200000$, $k=1$, также в этой подзадаче нет третьего типа запроса. Оценивается в 9 баллов.
5. $1 <= n, q <= 200000$, также в этой подзадаче нет третьего типа запроса. Оценивается в 12 баллов.
6. Ограничения из условия. Оценивается в 43 баллов.

Пример:

Вход

3 2 8
3 1 2
1 2
2 3
4 2 1
4 2 2
1 1 3
4 3 2
3 1 2
4 3 2
2 1 3
4 3 1

Ответ

3
1
1
1
2

( Aidos Nurmash )

Комментарий/решение

показать/скрыть код

#python 3.10 -v
ver_edg_oper = list(map(int,input("Кол-во вершин, рёбер и операций: ").split()))
vertices = list(map(int,input("значение вершин: ").split()))
edges = [list(map(int,input("описание рёбер: ").split())) for _ in range(ver_edg_oper[1])]
operations = [list(map(int,input("описание операции: ").split())) for _ in range(ver_edg_oper[-1])]
#####################

graph = {vertices[i]:[] for i in range(len(vertices))}  # создал сет словаря: {n: [a[j+m]]}

for j in range(len(vertices)): # словарь заполняется данными из edges
	for edgeslist in edges: # происходит связь графов
		if vertices[j] in edgeslist: # к каждой вершине добавляются рёбра
 			graph[vertices[j]].append(edgeslist) # которые создают связь с другими вершинами

for i in range(len(graph)): #соединил все связанные вершины в единый список и создал это во множество
	graph[vertices[i]] = set([i[j] for i in graph[vertices[i]] for j in range(len(i))])

[graph[vertices[i]].discard(vertices[i]) for i in range(len(vertices)) if vertices[i] in graph[vertices[i]]] #исключил связь вершины со своим значением

for i in graph: graph[i] = list(graph[i]) # преобразовал множество в список, так как сет невозможно редактировать и обращаться по индексу.

# Работа с операциями
for i in range(len(operations)):	
	if operations[i][0] == 1: # добавление ребра к u - v вершинам. Создание связи.
		graph[operations[i][1]].append(operations[i][2]);	graph[operations[i][2]].append(operations[i][1])

	elif operations[i][0] == 2: # удаление рёбра у u - v вершин. Лишение связи.
		graph[operations[i][1]].remove(operations[i][2]); graph[operations[i][2]].remove(operations[i][1])				

	elif operations[i][0] == 3: # перестановка местами вершин. 
		graph[operations[i][1]],graph[operations[i][2]] = graph[operations[i][2]],graph[operations[i][1]]
	else: # соседние вершины u сортировать по возрастанию и вывести v значение 
		print(sorted([i for i in graph[operations[i][1]]],reverse=True)[operations[i][2]-1])

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