Cod sursa(job #1765847)

Utilizator mircea_marian.popaPopa Mircea-Marian mircea_marian.popa Data 27 septembrie 2016 01:21:08
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.75 kb
#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;
}