Cod sursa(job #1154713)

Utilizator IonSebastianIon Sebastian IonSebastian Data 26 martie 2014 12:32:45
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int MAX_N = 32000;

int n, m, p, x, y, a, b, c, d, niv;
int minim[16][MAX_N+1], t[16][MAX_N+1], bombe[16][MAX_N+1], nivel[MAX_N+1];
int logn;

vector<int> vecini[MAX_N+1];

int log2(int x)
{
    if(x == 1)
    {
        return 0;
    }
    int nr = 0;
    while(x != 1)
    {
        x /= 2;
        nr++;
    }
    return nr;
}

void dfs(int tata)
{
    int i, fiu;
    //euler[1][++nr] = tata;
    //poz[tata] = nr;
    for(i = 0;i < vecini[tata].size(); i++)
    {
        fiu = vecini[tata][i];
        nivel[fiu] = ++niv;
        dfs(fiu);
        //euler[1][++nr] = tata;
    }
}

int min(int a, int b)
{
    return (a < b) ? a:b;
}

int bsearch(int a, int b)
{
    int pas = logn;
    while(pas != 0)
    {
        if(nivel[t[pas][a]] >= nivel[b])
        {
            a = t[pas][a];
        }
        pas--;
    }
    return a;
}

int binaryLCA(int x, int y)
{
    int pas = logn;
    while(pas != 0)
    {
        if(t[pas][x] != t[pas][y])
        {
            x = t[pas][x];
            y = t[pas][y];
        }
        pas--;
    }
    return x;
}

int main()
{
    int i, j, rez;
    in >> n >> m >> p;
    for(i = 2; i <= n; i++)
    {
        in >> t[0][i] >> bombe[0][i];
        vecini[t[0][i]].push_back(i);
    }
    logn = log2(n);
    for(i = 1; i <= logn; i++)
    {
        for(j = 1; j <= n; j++)
        {
            t[i][j] = t[i-1][t[i-1][j]];
        }
    }
    for(j = 1; j <= n; j++)
    {
        minim[0][j] = bombe[0][j];
    }
    for(i = 1; i <= logn; i++)
    {
        for(j = 1; j <= n; j++)
        {
            minim[i][j] = min(minim[i-1][j], minim[i-1][t[i-1][j]]);
        }
    }
    in >> x >> y >> a >> b >> c >> d;
    int xprim, yprim;
    for(i = 1; i <= m; i++)
    {
        xprim = x;
        yprim = y;
        if(nivel[x] > nivel[y])
        {
            xprim = bsearch(x, y);
        } else if(nivel[x] < nivel[y])
        {
            yprim = bsearch(y, x);
        }
        rez = minim[0][binaryLCA(xprim, yprim)];
        if(i > m-p)
        {
            out << rez << "\n";
        }
        x = (x*a + y*b)%n + 1;
        y = (y*c + rez*d)%n + 1;
    }
    return 0;
}