Pagini recente » Cod sursa (job #2647628) | Cod sursa (job #1134360) | Cod sursa (job #2912458) | Cod sursa (job #2020378) | Cod sursa (job #1765847)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
struct myList {
unsigned short info;
myList *next;
};
struct treeNod {
unsigned short parent, level, ancestor, section;
unsigned int numOfBombs, costToAncestor;
myList *firstChild, *lastChild;
treeNod(){
firstChild = lastChild = NULL;
parent = 32001;
}
void addChild(unsigned short chi){
myList *newCh = new myList;
newCh->info = chi;
newCh->next = NULL;
if( lastChild != NULL ){
lastChild->next = newCh;
lastChild = newCh;
} else
firstChild = lastChild = newCh;
}
void removeChildren(void){
myList *ch1 = firstChild, *ch2;
while(ch1 != NULL){
ch2 = ch1;
ch1 = ch1->next;
delete ch2;
}
}
void printNode(void){
myList *newCh = firstChild;
cout << "parent: " << parent << ", level: " << level << ", section: " << section <<
", ancestor: " << ancestor << ", numberOfBombs: " << numOfBombs << ", costToAncestor: " << costToAncestor << endl;
cout << "children :";
while( newCh ){
cout << newCh->info << " ";
newCh = newCh->next;
}
cout << endl;
}
};
struct myQueue {
myList *out, *in;
myQueue(){
in = out = NULL;
}
void addEl(unsigned short el){
myList *newCh = new myList;
newCh->info = el;
newCh->next = NULL;
if( in == NULL )
in = out = newCh;
else{
in->next = newCh;
in = newCh;
}
}
unsigned short removeEl(){
unsigned short rez = out->info;
myList *lll = out;
out = out->next;
delete lll;
if( out == NULL )
in = NULL;
return rez;
}
bool isEmpty(){
if( out == NULL )
return true;
return false;
}
void print(void){
myList *i = out;
cout << "qu: ";
while(i){
cout << i->info << " ";
i = i->next;
}
cout << "\n";
}
};
unsigned short maxH, N, A, B, C, D;
treeNod *tree;
unsigned int getCost(unsigned short X,
unsigned short Y){
if( X == Y )
return 0;
unsigned int cost = 100001;
while( tree[X].section != tree[Y].section ){
if( tree[X].section < tree[Y].section ){
if( cost > tree[Y].costToAncestor )
cost = tree[Y].costToAncestor;
Y = tree[Y].ancestor;
if( cost > tree[Y].numOfBombs )
cost = tree[Y].numOfBombs;
Y = tree[Y].parent;
} else {
if( cost > tree[X].costToAncestor )
cost = tree[X].costToAncestor;
X = tree[X].ancestor;
if( cost > tree[X].numOfBombs )
cost = tree[X].numOfBombs;
X = tree[X].parent;
}
}
while( X != Y ){
if( tree[X].level < tree[Y].level ){
if( cost > tree[Y].numOfBombs )
cost = tree[Y].numOfBombs;
Y = tree[Y].parent;
} else {
if( cost > tree[X].numOfBombs )
cost = tree[X].numOfBombs;
X = tree[X].parent;
}
}
return cost;
}
void formulaIndexes(unsigned short& X, unsigned short& Y, unsigned short& Z){
Z = getCost(X,Y);
X++;
Y++;
X = (X * A + Y * B) % N;
Y = (Y * C + Z * D) % N;
}
int main(){
fstream fis;
fis.open("atac.in", ios::in);
unsigned short i, X, Y, root, Z;
unsigned int P, M, nB;
maxH = 0;
fis >> N >> M >> P;
tree = new treeNod [N];
i = 2;
while( i <= N ){
fis >> A >> nB;
i--;
A--;
if( tree[A].parent == 32001 ){
tree[A].parent = i;
tree[i].addChild(A);
tree[A].numOfBombs = nB;
} else {
tree[i].parent = A;
tree[A].addChild(i);
tree[i].numOfBombs = nB;
}
i+=2;
}
fis >> X >> Y >> A >> B >> C >> D;
X--;
Y--;
fis.close();
for( i = 0 ; i < N ; i++ )
if( tree[i].parent == 32001 ){
tree[i].level = 0;
root = i;
break;
}
myQueue qu;
myList *j;
qu.addEl(root);
tree[root].level = 0;
while( !qu.isEmpty() ){
i = qu.removeEl();
j = tree[i].firstChild;
tree[i].level++;
while( j != NULL ){
tree[j->info].level = tree[i].level;
qu.addEl(j->info);
j = j->next;
}
tree[i].level--;
if( tree[i].lastChild == NULL && maxH < tree[i].level )
maxH = tree[i].level;
}
maxH = (unsigned short)sqrt(maxH);
qu.addEl(root);
while( !qu.isEmpty() ){
i = qu.removeEl();
tree[i].section = tree[i].level/maxH;
//calculate ancestor and number of bombs and section
if( tree[i].level % maxH == 0 ){
tree[i].ancestor = i;
tree[i].costToAncestor = 100001;
} else {
tree[i].ancestor = tree[tree[i].parent].ancestor;
tree[i].costToAncestor = (tree[tree[i].parent].costToAncestor < tree[i].numOfBombs) ?
tree[tree[i].parent].costToAncestor : tree[i].numOfBombs;
}
//add children to qu
j = tree[i].firstChild;
while( j ){
qu.addEl(j->info);
j = j->next;
}
}
maxH = M - P;
for(i = 1 ; i <= maxH ; i++)
formulaIndexes(X , Y, Z);
fis.open("atac.out", ios::out);
for( i = M - P + 1 ; i <= M ; i++ ){
formulaIndexes(X , Y, Z);
fis << Z << endl;
}
fis.close();
for( i = 0 ; i < N ; i++ )
tree[i].removeChildren();
delete [] tree;
}