• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Bezpieczeństwo Letni Obóz treningowy przed EJOI, grafy. Bład w kodzie.

Aruba Cloud VPS - 50% taniej przez 3 miesiące!
0 głosów
403 wizyt
pytanie zadane 2 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Mam problem z takim zadaniem: https://sio2.mimuw.edu.pl/c/oij15-wiekuisty-oboz/p/bez/

Wydaje mi się, że wystarczy zliczyć liczbę liści, i wynik to (liczba_liści + 1) / 2, bo łączymy każde dwa liście. Dostaję 52pkt(podejrzewam, że tylko pierwszy wiersz wejścia wypisuję dobrze, bo pisze ograniczenie, że tylko za pierwszy wiersz dobry jest 50pkt), kompletnie nie wiem gdzie jest błąd, debuguję już chyba z godzinę i nie dowieżam co się dzieje. W wypisywaniu poprostu siłowo paruję każde dwa liście.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, a = 0, b = 0;
vector<int> ile_wchodzi;
vector<int> jakie_maja_stopien_jeden;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    if (n == 1)
    {
        cout << "0" << '\n';
        return 0;
    }
    ile_wchodzi.assign(n+1,0);
    for (int i = 0; i < n-1; ++i)
    {
        cin >> a >> b;
        ile_wchodzi[a]++;
        ile_wchodzi[b]++;
    }

    for (int i = 1; i <= n; ++i)
        if (ile_wchodzi[i] == 1)
            jakie_maja_stopien_jeden.push_back(i);

    cout << (jakie_maja_stopien_jeden.size() + 1) / 2 << '\n';
    if (jakie_maja_stopien_jeden.size() % 2 == 0)
    {
        for (int i = 0; i < jakie_maja_stopien_jeden.size(); i+=2)
            cout << jakie_maja_stopien_jeden[i] << ' ' << jakie_maja_stopien_jeden[i+1] << '\n';
    }
    else
    {
        for (int i = 0; i < jakie_maja_stopien_jeden.size() - 1; i+=2)
            cout << jakie_maja_stopien_jeden[i] << ' ' << jakie_maja_stopien_jeden[i+1] << '\n';
        cout << jakie_maja_stopien_jeden[0] << ' ' << jakie_maja_stopien_jeden[jakie_maja_stopien_jeden.size()-1] << '\n';
    }

    return 0;
}

 

1 odpowiedź

+1 głos
odpowiedź 2 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
wybrane 2 kwietnia 2023 przez pasjonat_algorytmiki
 
Najlepsza

Zobacz test:

7
1 2
1 3
2 4
2 5
3 6
3 7

Co jak połączysz 4 z 5 oraz 6 z 7. Czy to będzie dobrze?

komentarz 2 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
złe, to jak to można zrobić?
komentarz 2 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
Nie poddawaj się tak szybko :) Pomyśl jeszcze trochę nad tym
komentarz 3 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Narazie mam pomysł jedynie jak w O(N^2) to zrobić. Ma to coś wspólnego z dwóspójnymi składowymi / mostami / punktami artykulacji (wyczytałem kiedyś, że jest coś takiego, tylko jeszcze nwm co)?
komentarz 3 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
Jak wygląda ten pomysł w O(N^2)? W drzewie praktycznie wszystko jest mostem, punktem artykulacji, więc chyba się nie przyda
komentarz 3 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Jak usuniemy jakąś krawędź, to drzewo dzięki się na dwa mniejsze drzewa. Mój pomysł był taki, że jeśli liczba liści w całym drzewie jest parzysta, to szukamy takiej krawedzi, że w obu drzewach jest tyle samo liści i losowo uzupełniamy, a jak nieparzysta to szukamy podziału, że w jednym po drzewie jest o jeden liść więcej.
komentarz 3 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Ale jak teraz o tym myślę, to już nie wiem czy to jest dobre, chyba się wywali....
komentarz 3 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)

Ja tak szczerze nie wiem jak to zrobić. Zrobiłem mały research i wygląda na to że to zadanie pojawiło się na BOI. Tu jest niby jakieś rozwiązanie 

komentarz 3 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Szkoda, że do tych zadań z tego obozu nie ma rozwiązań, zadania są epickie, ale brakuje jakieś książeczki / omówień.....
komentarz 3 kwietnia 2023 przez Whistleroosh Maniak (57,360 p.)
Dlatego lepiej robić trudne zadanka jeśli są do nich solvy. Te zadania z EJOI są całkiem trudne, na OI by się nadały bez problemu

Podobne pytania

0 głosów
1 odpowiedź 593 wizyt
0 głosów
1 odpowiedź 751 wizyt
0 głosów
1 odpowiedź 158 wizyt

93,115 zapytań

142,097 odpowiedzi

321,678 komentarzy

62,453 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...