Zadanie z UVA, błędna odpowiedź

0

Próbowałem zrobić Problem 115 - Climbing Trees z uva.onlinejudge.org: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=51

Streszczenie zadania: Na wejściu jest najpierw ciąg par dziecko-rodzic, a potem dla każdej pary węzłów z wejścia trzeba wypisać „pokrewieństwo” między nimi: a więc (great … great grand) parent / child jeśli któryś z tych węzłów jest potomkiem drugiego w linii prostej, sibling jeśli mają wspólnego rodzica, i k cousin (removed j) dla bardziej skomplikowanych sytuacji, wreszcie no relation jeśli nie są w tym samym drzewie.

Sprawdzarka ciągle wypluwa mi Wrong Answer. Testy przykładowe, ten ze specyfikacji zadania i ten z http://www.udebug.com/UVa/115 oczywiście mi przechodzą poprawnie.

Na forum UVA, w temacie tego zadania https://uva.onlinejudge.org/board/viewtopic.php?f=1&t=2334&hilit=115 twierdzili, że na wejściu pojawiają się węzły, które mają kilku rodziców; jednak sprawdziłem dowodnie ( http://ideone.com/etjrQJ ) że tak nie jest, że węzły podane na wejściu mają najwyżej jednego rodzica i tworzą jednego lub kilka DAGów.

Na tymże forum pojawiały się też testy, które zakładały, że na wejściu mogą pojawić się żądania sprawdzenia relacji między tym samym elementem. Ponownie jednak, sprawdziłem dowodnie ( http://ideone.com/1QpV7n ) że tak nie jest, że na wejściu zawsze każą sprawdzać relacje między różnymi elementami.

Pozwoliłem sobie zatem zignorować testy z tamtejszego forum, które sprawdzają powyższe przykłady.

Oto moja próba rozwiązania zadania:

#include <iostream>
#include <string>
#include <unordered_map>
#include <stack>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct wezel
{
        wezel *rodzic = NULL;
};

unordered_map<string, wezel> wszystkieWezly;

void wszyscyRodzice(stack<wezel*> &s, wezel &p)
{
        s.push(&p); // By latwiej obslugiwac potomkow w linii prostej
        
        wezel *tmp = &p;
        while(tmp->rodzic != NULL)
        {
                tmp = tmp->rodzic;
                s.push(tmp);
        }
}

struct relacja
{
        bool spokrewnieni = true;
        int m, n; // -1 gdy sam jest Najnizszym Wspolnym Przodkiem (dziedziczenie w linii prostej)
        
        relacja(wezel &p, wezel &q)
        {
                stack<wezel*> rp;
                wszyscyRodzice(rp, p);
                stack<wezel*> rq;
                wszyscyRodzice(rq, q);
                
                if(rp.top() != rq.top()) // Brak wspolnego przodka
                        spokrewnieni = false;
                else
                {
                        while(!rp.empty() && !rq.empty() && rp.top() == rq.top())
                        {
                                rp.pop();
                                rq.pop();
                        }
                        m = rp.size()-1;
                        n = rq.size()-1;
                }                
        }
};

void wypiszGreaty(int g)
{
        for(; g > 1; g--)
                cout << "great ";
        if(g > 0)
                cout << "grand ";
}

void wypiszRelacje(relacja r)
{
        if(!r.spokrewnieni)
                cout << "no relation";
        else if(r.n == -1)
        {
                wypiszGreaty(r.m);
                cout << "child";
        }
        else if(r.m == -1)
        {
                wypiszGreaty(r.n);
                cout << "parent";
        }
        else
        {
                int k = min(r.m, r.n), j = abs(r.m - r.n);
                if(k==0 && j==0)
                        cout << "sibling";
                else
                {
                        cout << k << " cousin";
                        if(j>0)
                                cout << " removed " << j;
                }
        }
        
        cout << '\n';
}

int main()
{
        string p, q;
        bool wczytywanie = true;
        while(cin >> p >> q)
        {
                if(p != "no.child")
                {
                        wszystkieWezly.insert(make_pair(p, wezel()));
                        wszystkieWezly.insert(make_pair(q, wezel()));
                        
                        if(wczytywanie)
                                wszystkieWezly.at(p).rodzic = &wszystkieWezly.at(q);
                        else
                                wypiszRelacje(relacja(wszystkieWezly.at(p), wszystkieWezly.at(q)));
                }
                else
                        wczytywanie = false;
        }
}

Przepraszam bardzo... ale ma ktoś jakieś pomysły, co może być nie tak?
Bo mi się już skończyły...

0

Korzystałeś z możliwości generowania randomowego inputu na http://www.udebug.com/UVa/115 ?

0

Accepted nareszcie.

Problem: W żądaniach sprawdzenia relacji może pojawić się „no.child”; w takim wypadku nie należy tej linii ignorować, tylko wypisać „no relation”.

Znalezione w inputach użytkowników na udebug: http://www.udebug.com/UVa/115/input

BTW: Random input mi się ciągle generuje jeden i ten sam...

1 użytkowników online, w tym zalogowanych: 0, gości: 1