Hafiz Batyrkhan


Есеп №1. 

Есеп F. Yosik - армандар орындалатын қала

Ограничение по времени:
1 second
Ограничение по памяти:
256 megabytes

Yosik - миллиондаған армандар орындалатын Қазақстанның қаласы. Сонымен бірге, Yosik - бүкіл әлемнің ең маңызды экономикалық орталығы. Yosik, Лондон және Токио сияқты, әлемдік экономиканың үш негізгі орталығының бірі деп аталады. Ал, әрине, CMaster мэрі болмаса, қала мұндай танымалдылыққа ие болмас еді. Ол осы мақсатқа жету үшін бар күш-жігерін салған. Бірақ басқа елдер арасындағы экономикалық текетірес Yosik экономикасына теріс әсер етті. Мэр қалада кейбір жолдардың сапасын жақсартқысы келеді. Ал қалада $n$ аудан бар. Әр ауданның экономикалық жағдайы екі түрлі сөзбен сиппаталады: Жоғары немесе Төмен. Мэр CMaster қаланың жолдарды дағдарыс кезінде жақсарту туралы дұрыс шешім қабылдауы үшін, ол осы жол қанша жағдайы Жоғары екі ауданның арасында орналасқанын білуі қажет. Яғни екі ауданның арасындағы бағыттардың бәрі осы жолдан өтсе ғана, жол өте Жоғары маңыздылықтары бар $(a, b)$ аудандарын біріктіреді. Және $q$ түрлі оқиғалар бар: 1) $v$ $(1 <=q v <=q n)$ ауданының статусын өзгерту, Төмен болса, Жоғары, әйтпесе оны Төменге өзгертіңіз. 2) $i$-ші $(1 <=q i <=q m)$ жол үшін, осы жол біріктіретін Жоғарғы маңыздылығы бар $(a, b)$ екі қаланың санын айтыңыз, яғни осы жол Жоғары мәртебесі бар $(a, b)$ арасындағы барлық бағыттарда орналасқан аудандарының санын айтыңыз. Ал жұптар $(a, b)$ және $(b, a)$ бірдей деп есептеледі. Қаланы $n$ шыңдары және $m$ жолдары бар байланыстырылған бағытталмаған граф ретінде көрсетуге болады. Әрбір ауданның Жоғары немесе Төмен экономикалық маңызы бар. Бастапқыда барлық аудандардың экономикалық маңызы Төмен. Ауданды өзімен байланыстыратын жол болуы мүмкін (ілмек), бірақ бірнеше бірдей жолдар жоқ, яғни бірдей екі шыңды жалғайтын жолдар жоқ.
Формат входного файла
Бірінші жолда $n$, $m$ және $q$, облыстардың саны, жолдар мен оқиғалар саны берілген. Содан кейін $m$ сан берілген - Yosik-тегі бағытталмаған жолдар. Графта екі бірдей жолдар жоқ, бірақ ілмектер болуы мүмкін. Содан кейін сізге $q$ сұранымдар $(type, number)$ беріледі. Егер $type = 1$ болса, онда бұл сұрақтың бірінші түрі және number, $(1 <=q number <=q n)$ шыңның санын көрсетеді. Егер $type = 2$ болса, онда бұл сұраулардың екінші түрі және $number$, $(1 <=q number <=q m)$ - кірістің деректерінің реті бойынша жол санын білдіреді.
Формат выходного файла
2-нші түрдің әрбір сұрауы үшін, сіз осы жол қанша маңыздылығы Жоғары шыңдардың $(a, b)$ арасындағы барлық бағыттарда орналасқанын табыңыз
Система оценки
Бұл есепте бес қосалқы тапсырма бар: 1. $1 <=q n, q <=q 10$. Тапсырма 10 ұпаймен бағаланады 2. $1 <=q n, m, q <=q 300$. Тапсырма 14 ұпаймен бағаланады 3. $1 <=q n, m, q <=q 2000$. Тапсырма 22 ұпаймен бағаланады 4. Қала ағаш түрінде берілген $1 <=q n, q <=q 10^5, m = n - 1$. Тапсырма 24 ұпаймен бағаланады 5. $1 <=q n, m, q <=q 10^5$. Тапсырма 30 ұпаймен бағаланады
Пример:
\exmpfile{example.01}{example.01.a}%
Замечание
Бірінші мысалдағы қала нұсқасы (5-нші оқиғаға дейін) \begin{center} \includegraphics[width=10cm,height=7cm]{image.eps} \end{center} 1-нші жол, яғни белгіленіп тұрған жол 2 әртүрлі аудан жұптарының арасында жатқанын байқауға болады: (1, 2) және (1, 4). Бірақ (2, 4) арасындағы жол 2 және 4 аудандарын (2 -> 3 -> 4) бағыты болғандықтан байланыстырмайды ( Hafiz Batyrkhan )
комментарий/решение(6) олимпиада
Есеп №2. 

Есеп F. Yosik - армандар орындалатын қала

Ограничение по времени:
1 second
Ограничение по памяти:
256 megabytes

Yosik - миллиондаған армандар орындалатын Қазақстанның қаласы. Сонымен бірге, Yosik - бүкіл әлемнің ең маңызды экономикалық орталығы. Yosik, Лондон және Токио сияқты, әлемдік экономиканың үш негізгі орталығының бірі деп аталады. Ал, әрине, CMaster мэрі болмаса, қала мұндай танымалдылыққа ие болмас еді. Ол осы мақсатқа жету үшін бар күш-жігерін салған. Бірақ басқа елдер арасындағы экономикалық текетірес Yosik экономикасына теріс әсер етті. Мэр қалада кейбір жолдардың сапасын жақсартқысы келеді. Ал қалада $n$ аудан бар. Әр ауданның экономикалық жағдайы екі түрлі сөзбен сиппаталады: Жоғары немесе Төмен. Мэр CMaster қаланың жолдарды дағдарыс кезінде жақсарту туралы дұрыс шешім қабылдауы үшін, ол осы жол қанша жағдайы Жоғары екі ауданның арасында орналасқанын білуі қажет. Яғни екі ауданның арасындағы бағыттардың бәрі осы жолдан өтсе ғана, жол өте Жоғары маңыздылықтары бар $(a, b)$ аудандарын біріктіреді. Және $q$ түрлі оқиғалар бар: 1) $v$ $(1 <=q v <=q n)$ ауданының статусын өзгерту, Төмен болса, Жоғары, әйтпесе оны Төменге өзгертіңіз. 2) $i$-ші $(1 <=q i <=q m)$ жол үшін, осы жол біріктіретін Жоғарғы маңыздылығы бар $(a, b)$ екі қаланың санын айтыңыз, яғни осы жол Жоғары мәртебесі бар $(a, b)$ арасындағы барлық бағыттарда орналасқан аудандарының санын айтыңыз. Ал жұптар $(a, b)$ және $(b, a)$ бірдей деп есептеледі. Қаланы $n$ шыңдары және $m$ жолдары бар байланыстырылған бағытталмаған граф ретінде көрсетуге болады. Әрбір ауданның Жоғары немесе Төмен экономикалық маңызы бар. Бастапқыда барлық аудандардың экономикалық маңызы Төмен. Ауданды өзімен байланыстыратын жол болуы мүмкін (ілмек), бірақ бірнеше бірдей жолдар жоқ, яғни бірдей екі шыңды жалғайтын жолдар жоқ.
Формат входного файла
Бірінші жолда $n$, $m$ және $q$, облыстардың саны, жолдар мен оқиғалар саны берілген. Содан кейін $m$ сан берілген - Yosik-тегі бағытталмаған жолдар. Графта екі бірдей жолдар жоқ, бірақ ілмектер болуы мүмкін. Содан кейін сізге $q$ сұранымдар $(type, number)$ беріледі. Егер $type = 1$ болса, онда бұл сұрақтың бірінші түрі және number, $(1 <=q number <=q n)$ шыңның санын көрсетеді. Егер $type = 2$ болса, онда бұл сұраулардың екінші түрі және $number$, $(1 <=q number <=q m)$ - кірістің деректерінің реті бойынша жол санын білдіреді.
Формат выходного файла
2-нші түрдің әрбір сұрауы үшін, сіз осы жол қанша маңыздылығы Жоғары шыңдардың $(a, b)$ арасындағы барлық бағыттарда орналасқанын табыңыз
Система оценки
Бұл есепте бес қосалқы тапсырма бар: 1. $1 <=q n, q <=q 10$. Тапсырма 10 ұпаймен бағаланады 2. $1 <=q n, m, q <=q 300$. Тапсырма 14 ұпаймен бағаланады 3. $1 <=q n, m, q <=q 2000$. Тапсырма 22 ұпаймен бағаланады 4. Қала ағаш түрінде берілген $1 <=q n, q <=q 10^5, m = n - 1$. Тапсырма 24 ұпаймен бағаланады 5. $1 <=q n, m, q <=q 10^5$. Тапсырма 30 ұпаймен бағаланады
Пример:
\exmpfile{example.01}{example.01.a}%
Замечание
Бірінші мысалдағы қала нұсқасы (5-нші оқиғаға дейін) \begin{center} \includegraphics[width=10cm,height=7cm]{image.eps} \end{center} 1-нші жол, яғни белгіленіп тұрған жол 2 әртүрлі аудан жұптарының арасында жатқанын байқауға болады: (1, 2) және (1, 4). Бірақ (2, 4) арасындағы жол 2 және 4 аудандарын (2 -> 3 -> 4) бағыты болғандықтан байланыстырмайды ( Hafiz Batyrkhan )
комментарий/решение(6) олимпиада