This is my first post here, and I would like apologize for my English. I'm bad in C++ and I wrote this code without a lot of research in C++. Despite this I achieved my goal and I have correct results buuut... only on Windows 10 (codeblocks). When I try debug in Linux the scores are different. For instance, with the following input:
5
5 0
3 0
3 5
5 1
3 3
On Windows I get the correct result:
2
4
5
1
3
But on Linux or on https://www.programiz.com/cpp-programming/online-compiler/ (probably a Linux server?) I get:
0
0
5
1
3
To my mind, the issue is in memory... but I've been finding faults for many hours without results.
#include <iostream>
#include <list>
#include <stack>
using namespace std;
class node
{
public:
int id=0;
int klucz=0;
int rodzic=0;
int idzzerem=0;
int ilezzerem=0;
list<int> dzieci;
};
bool spr(node a, node b)
{
return a.klucz<b.klucz;
}
int ilezzerem(node drzewo[],int korzen,int pom=0)
{
if(drzewo[korzen].ilezzerem==0)
return 0;
else if(drzewo[korzen].ilezzerem==1)
return drzewo[korzen].ilezzerem + ilezzerem(drzewo,drzewo[korzen].idzzerem);
else
{
while(!drzewo[korzen].dzieci.empty())
{
int a = drzewo[korzen].dzieci.front();
drzewo[korzen].dzieci.pop_front();
pom+= ilezzerem(drzewo,a,pom);
}
return pom+drzewo[korzen].ilezzerem;
}
}
int main()
{
ios_base::sync_with_stdio(false);
int rodzic,klucz,nIloscWezlow,a;
std::stack<int> P,K,M;
int i=1;
cin>>nIloscWezlow;
node drzewo[nIloscWezlow+1];
bool klucze[nIloscWezlow+1];
klucze[0]=false;
bool niejedn[nIloscWezlow+1];
niejedn[0]=false;
while(i<=nIloscWezlow)
{
cin>>rodzic>>klucz;
if(klucz>0)
{
klucze[klucz]=true;
drzewo[i].klucz=klucz;
}
drzewo[i].id=i;
if(i==rodzic&&klucz==0)
drzewo[rodzic].klucz=1;
else
drzewo[i].rodzic=rodzic;
if(klucz==0)
{
drzewo[rodzic].dzieci.push_front(i);
drzewo[rodzic].idzzerem=i;
drzewo[rodzic].ilezzerem++;
klucze[klucz]=false;
}
niejedn[i]=false;
i++;
}
for(int k=nIloscWezlow;k>0;k--)
{
if(klucze[k]==false)
{
P.push(k);
K.push(k);
}
}
list<node> listaIDPoddrzewDoBadania;
for (int k = 1;k<=nIloscWezlow;k++)
{
node obecny1 = drzewo[k];
if(obecny1.ilezzerem>0&&obecny1.klucz!=0)
listaIDPoddrzewDoBadania.push_front(obecny1);
}
listaIDPoddrzewDoBadania.sort(spr);
while(!listaIDPoddrzewDoBadania.empty()&&!P.empty())
{
node obecny = listaIDPoddrzewDoBadania.front();
listaIDPoddrzewDoBadania.pop_front();
int idobecnego = obecny.id;
int ilezdjackluczy = ilezzerem(drzewo,idobecnego);
while(ilezdjackluczy!=0)
{
int kluczdowlozeniawM = K.top();
K.pop();
M.push(kluczdowlozeniawM);
ilezdjackluczy--;
}
int elementzeszczytu=0;
if(!K.empty())
elementzeszczytu = K.top();
if(elementzeszczytu>obecny.klucz ||K.empty())
{
node current = obecny;
while(current.ilezzerem==1)
{
int dowstawienia = M.top();
M.pop();
drzewo[current.idzzerem].klucz=dowstawienia;
if(drzewo[current.idzzerem].klucz==0)
break;
current=drzewo[current.idzzerem];
}
int pomDlaP = P.top();
while(pomDlaP<obecny.klucz && !P.empty())
{
P.pop();
if(!P.empty())
pomDlaP= P.top();
}
}
else if(elementzeszczytu<obecny.klucz)
{
int pomDlaP = P.top();
while(pomDlaP<obecny.klucz && !P.empty())
{
niejedn[pomDlaP]=true;
P.pop();
if(!P.empty())
pomDlaP= P.top();
}
}
else
continue;
}
for (int koniec = 1;koniec<=nIloscWezlow;koniec++)
{
if(niejedn[drzewo[koniec].klucz])
cout<<0<<endl;
else
cout<<drzewo[koniec].klucz<<endl;
}
}