Masala #ZHAPJF2ELT
Nosoz kabellar
Shaharda \(n\) ta stansiya va \(m\) ta ikki tomonlama kabel bor. Tarmoq kaktus graf, ya'ni har bir kabel ko'pi bilan bitta oddiy siklga tegishli.
Har bir kabelning holati \(0\) yoki \(1\). Holat \(1\) bo'lsa, kabel nosoz deb hisoblanadi. Muhandis bir amalda bitta stansiyani tanlaydi va shu stansiyaga ulangan barcha kabellarning holatini teskarisiga o'zgartiradi: \(0\) holatlar \(1\) ga, \(1\) holatlar \(0\) ga aylanadi.
Keyin \(q\) ta hodisa bo'ladi. Har bir hodisada bitta kabelning holati tashqi sabab bilan teskarisiga o'zgaradi. Har bir hodisadan keyin muhandis istalgancha amallar bajarishi mumkin.
Har bir hodisadan keyin mumkin bo'lgan eng kichik nosoz kabellar sonini toping.
Ushbu masala IOI-uslubida baholanadi. Testlar quyidagi subtasklarga bo'lingan.
Subtakslar:
\(1\)) \(10\) ball, \(n \le 8\), \(q \le 20\)
\(2\)) \(15\) ball, Graf daraxt
\(3\)) \(20\) ball, Grafda aynan bitta oddiy sikl bor
\(4\)) \(25\) ball, \(q \le 2000\)
\(5\)) \(30\) ball, Qo'shimcha cheklov yo'q
Birinchi qatorda uchta butun son \(n\), \(m\), \(q\) beriladi: \(1 \le n \le 2 \cdot 10^5\), \(0 \le m \le 3 \cdot 10^5\), \(0 \le q \le 2 \cdot 10^5\).
Keyingi \(m\) ta qatorda uchta butun son \(u_i\), \(v_i\), \(s_i\) beriladi: \(1 \le u_i, v_i \le n\), \(u_i \ne v_i\), \(s_i \in \{0,1\}\).
Bu yerda \(u_i\) va \(v_i\) kabel ulangan stansiyalar, \(s_i\) esa kabelning boshlang'ich holati.
Graf bog'langan va kaktus graf ekani kafolatlanadi. \(m = 0\) faqat \(n = 1\) bo'lganda mumkin.
Keyingi \(q\) ta qatorda bittadan butun son \(e_j\) beriladi \((1 \le e_j \le m)\). Bu hodisada \(e_j\)-kabel holati teskarisiga o'zgaradi.
Har bir hodisadan keyin bitta qatorda mumkin bo'lgan eng kichik nosoz kabellar sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 4 4 1 2 0 2 3 1 3 1 0 3 4 1 1 4 2 3 |
0 0 1 0 |
| 2 |
6 7 5 1 2 1 2 3 0 3 1 1 3 4 0 4 5 0 5 6 1 6 3 0 4 2 7 1 6 |
0 1 2 1 0 |
Namunadagi 1-testda:
Birinchi hodisadan keyin 111-kabel holati o'zgaradi. Agar 222- va 444-stansiyalarda amal bajarilsa, barcha kabellar soz holatga keladi, shuning uchun javob 000.
Ikkinchi hodisadan keyin 444-kabel holati o'zgaradi. Bu safar faqat 222-stansiyada amal bajarish yetarli bo'ladi va yana nosoz kabel qolmaydi. Javob 000.
Uchinchi hodisadan keyin 222-kabel holati o'zgaradi. Bu holatda barcha kabellarni bir vaqtda soz holatga keltirib bo'lmaydi. Masalan, hech qanday amal bajarmasak, faqat 111-kabel nosoz qoladi. Shuning uchun eng kichik qiymat 111.
To'rtinchi hodisadan keyin 333-kabel holati o'zgaradi. Agar 222-, 333- va 444-stansiyalarda amal bajarilsa, barcha kabellar soz holatga keladi. Javob 000.
Telegram kanalimizga obuna bo'ling