Cod sursa(job #2762539)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 7 iulie 2021 23:45:46
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.04 kb
/*
    Am adaugat ceva la liniile 73-75
*/
/*
    Functia minimPeLant la mine face o chestie foarte idioata
    nu incercati sa cititi sursa, cautati alta
*/

#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 32000 //treizeci si doi de mii
#define LOGMAXN 14 //[ log 2 (32 000) ]
#define INFINIT 100001 //o suta de mii unu

using namespace std;

ifstream fin ("atac.in");
ofstream fout ("atac.out");

int N, M, P;

int REZ; //global!!
int tt[LOGMAXN + 1][NMAX + 1];
int mn[LOGMAXN + 1][NMAX + 1];
int depth[NMAX + 1];

vector <int> fii[NMAX + 1]; //doar ca sa prelucrez depth[]

int putereDoiLowerbound(int VAL){
    int lo = -1;
    int hi = LOGMAXN + 1; //[ log 2 (NMAX) ] + 1

    while(hi - lo > 1){
        int mid = lo + (hi - lo) / 2;

        if( (1 << mid) <= VAL ){
            lo = mid;
        }
        else {
            hi = mid;
        }
    }

    return lo;
}


int nodNouDepth(int nod, int depthNou){
    //printf("Il urc pe %d\n", nod);
    //printf("nod = %d\n", nod);

    while(depth[nod] != depthNou){
        //caut binar cea mai mare putere a lui 2 cu care pot sa urc in arbore incat sa nu depasesc depthNou

        int urcare = putereDoiLowerbound(depth[nod] - depthNou);

        REZ = min(REZ, mn[urcare][nod]);
        nod = tt[urcare][nod];

        //printf("nod = %d\n", nod);
    }
    //printf("\n");

    return nod;
}

int minimPeLant(int A, int B){
    //mai intai vreau sa le aduc la acelasi depth
    //printf("Query pe (%d, %d)\n", A, B);

    if(A == B){
        return 0;
    }

    REZ = INFINIT;

    if(depth[A] > depth[B]){
        swap(A, B);
    }

    B = nodNouDepth(B, depth[A]);

    //acum urc cu puteri ale lui 2 pana dau de LCA
    while(A != B){
        int lo = -1;
        int hi = -1 + 1;
        for(int i = 0; (1 << i) <= depth[A] - 2; i++){
            hi = i + 1;
        }

        //printf("hi = %d\n", hi);

        while(hi - lo > 1){
            int mid = lo + (hi - lo) / 2;

            int ttA = tt[mid][A];
            int ttB = tt[mid][B];

            if(ttA == ttB){
                hi = mid;
            }
            else {
                lo = mid;
            }
        }

        //printf("(A, B) = (%d, %d)\nUrc cu pas %d\n", A, B, lo);

        if(lo == -1){
            REZ = min(REZ, mn[0][A]);
            REZ = min(REZ, mn[0][B]);

            A = tt[0][A];
            B = tt[0][B];
        }
        else {
            REZ = min(REZ, mn[lo][A]);
            REZ = min(REZ, mn[lo][B]);

            A = tt[lo][A];
            B = tt[lo][B];
        }
    }

    //printf("Sfarsit query!\n\n");

    return REZ;
}

void prelucrareTati(){
    for(int j = 1; j <= LOGMAXN; j++){
        for(int i = 1; i <= N; i++){
            if( (1 << j) - 1 <= depth[i] ){
                tt[j][i] = tt[j - 1][ tt[j - 1][i] ];
            }
        }
    }
}

void prelucrareMinim(){
    for(int j = 1; j <= LOGMAXN; j++){
        for(int i = 1; i <= N; i++){
            if( (1 << j) <= depth[i] ){
                mn[j][i] = min( mn[j - 1][i], mn[j - 1][ tt[j - 1][i] ] );
            }
        }
    }
}

void DFS(int node){
    for(int i = 0; i < fii[node].size(); i++){
        int vec = fii[node][i];

        depth[vec] = depth[node] + 1;
        DFS(vec);
    }
}


int main()
{
    fin >> N >> M >> P;

    tt[0][1] = 1;
    mn[0][1] = INFINIT;
    for(int i = 2; i <= N; i++){
        fin >> tt[0][i] >> mn[0][i];

        fii[ tt[0][i] ].push_back(i); //doar pt DFS, pt aflarea depth[]
    }

    depth[1] = 1;
    DFS(1); //aleg 1 ca radacina


    prelucrareTati();
    prelucrareMinim();

    int X, Y, A, B, C, D;
    fin >> X >> Y >> A >> B >> C >> D;

    for(int question = 1; question <= M; question++){
        int raspuns = minimPeLant(X, Y);

        if(M - question + 1 <= P){
            fout << raspuns << "\n";
        }

        X = (X * A + Y * B) % N + 1;
        Y = (Y * C + raspuns * D) % N + 1;
    }

    return 0;
}