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

Есеп A. Қызық ойын

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

2 seconds

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

256 megabytes

Жақында Айдос ежелгі тау халықтарының тарихын зерттей отырып, өте қызық ойынға тап болды. Ойынды ойлап табушылар бойынша, бұл ойынның мәдениеттегі орны ерекше, кез келген жастағы адамның дедуктивті ойлау қабілетіне септігін тигізеді екен. Айдос ойынға қызығып, оның замануи баламасын ұсынды. Сізге басында $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])

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