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

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

Есеп B. Array

Сізге ұзындығы $k$ болатын $a$ массиві және ұзындықтары $k$ болатын $n$ массив берілген. Егер, $x$ массивы үшін, массивтың сандарының орындарын ауыстырғанда, әр $i$-ға $(1 <= i <= k)$ $x_{p_i} \equiv 0 \pmod{a_i}$ қағидасы орындалатын ұзындығы $k$ болатын $p$ сандар тізбегі табылатын болса, онда х массивы "әдемі" болып саналады. Сізге, барлық $(l, r)$ $(1 <= l <= r <= n)$ жұптарының ішінен, осы кесіндідегі әдемі массивтердің саны, әдемі емес массивтердің санынан көп болатын қанша жұп бар екенін табу керек. Бірінші жолда екі бүтін сан, n және $k$, $(1 <= n <= 10^5, 1 <= k <= 20)$ беріледі. Екінші жолда ұзындығы $k$ болатын $a$ массиві беріледі $(1 <= a_i <= 10^9)$. Келесі $n$ жолда ұзындықтары $k$ болатын $n$ массив беріледі, яғни $i$ $(1 <= i <= k)$ жолында $b_i$ массиві беріледі $(1 <= b_{ij} <= 10^9)$. Жалғыз жолда есептің жауабын шығарыңыз. Есеп төрт бөлімнен тұрады:

1. $1 <= n <= 1000, k = 1$. $15$ ұпайға есептеледі.
2. $1 <= n <= 1000, 1 <= k <= 8$. $19$ ұпайға есептеледі.
3. $1 <= n <= 100, 1 <= k <= 20$. $31$ ұпайға есептеледі.
4. $1 <= n <= 10^5, 1 <= k <= 8$. $35$ ұпайға есептеледі.

Вход

3 1
2
1
2
2

Ответ

4

$a \equiv 0 \pmod{b}$ дегеніміз $a$ саны $b$ санына қалдықсыз бөлінеді деген мағынаны білдіреді. Бірінші мысалда $(1, 1)$ және $(1, 2)$ жұптары жауапқа қосылмайды, себебі біреуінде әдемі массивтердің саны $0$ $(0 <= 1)$ және $1$ $(1 <= 1)$ болып табылады.

Есеп C. Маглдар шабуылдайды

Әлемдік ғаламтор $n$ шыңдармен және $n - 1$ қабырғаларынан құралады. Әр қабырға екі басқа-басқа шыңдарды жалғайды. Осы желіде кез-келген шыңнан басқа шыңдардың барлығына қабырғалар арқылы жетуге болады. Әр шың басында Сиқыршы тұрады. Сиқыршылар — өте жылы шырайлы жаратылыстар, дегенмен, олар тек жұптасып өмір сүре алады. 2 Сиқыршы көршілес шыңдарда тұрғанда ғана жұп құра алады. Әр Сиқыршы тек бір ғана жұп құра алады. Маглдар кейбір шыңдарды бұғаттап, сонымен қатар бұғатталған шыңдардағы Сиқыршыларды да қолға түсіруді шешті. Әр бұғаттау желінің $k$ бұғатталатын шыңдарынан тұрады. Әр бұғатталған шыңнан Маглар сол шыңдағы Сиқыршыны қолға түсіріп, алып кетеді. Бұғаттан кейін байбалам басталап, Сиқыршылар өзіне жұп ізестіреді. Егерде ең болмаса бір Сиқыршы өзіне жұп таба алмаса, Хаос орнайды. Назар аударыңыз, Сиқыршылар жұптар саны көп болатындай, жұптарға бөлінеді. Сиқыршыларда ықтимал бұғаттардың $q$ болжамдары бар. Әр болжам үшін, сол болжам орындалса Хаос орнайтынын анықтаңыз. Бірінші жолда екі сан $n$, $q$ ($1 <= n, q <= 5*10^5$) — шыңдар саны мен болжамдар саны берілген. Келесі $n-1$ жолда екі сан $u$, $v$ ($1 <= u, v <= n$) — арасында қабырғалары бар шыңдар берілген. Келесі $q$ жолда болжамдар берілген. Әр болжам $k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ түрінде — бұғатталған шыңдардың саны мен нөмерлері беріледі. Бос жермен бөлінген $q$ сан шығарыңыз. Әр бұғат үшін келген болжамдар ретінде, егер Сиқыршылар бір-біріне жұп таба алса $1$ (Хаос орнамаса), таба алмаса $0$ (Хаос орнаса) шығарыңыз. $sum(k)$ деген барлық болжамдардағы бұғатталған шыңдардың саны. Есеп 5 бөлімнен тұрады: 1. $1 <= n, q, sum(k) <= 3000$, 2 ден көп шыңмен жалғанған шың жоқ. Бөлім $13$ ұпайға бағаланады. 2. $1 <= n, q, sum(k) <= 3000$. Бөлім $17$ ұпайға бағаланады. 3. $1 <= n, q, sum(k) <= 100000$. Бөлім $22$ ұпайға бағаланады. 4. $1 <= n, q, sum(k) <= 100000$. $k_i <= 1$. Бөлім $19$ ұпайға бағаланады. 5. $1 <= n, q, sum(k) <= 500000$. Бөлім $29$ ұпайға бағаланады. Вход

3 3
1 2
2 3
1 1
1 2
1 3

Ответ

1 0 1