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...