Cod sursa(job #1690114)

Utilizator lacraruraduRadu Matei Lacraru lacraruradu Data 14 aprilie 2016 19:42:12
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <fstream>

using namespace std;

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

#define N 32005
#define LOGN 17
#define INF 2147483647

int n, m, p;
int t[N], cost[N];
int X, Y, A, B, C, D;
int lst[N], vf[N], urm[N], nvf = 0;
int e[2 * N], ne = 0, poz[N];
int nivel[N], niv = 0;
int r[2 * N][LOGN];
int lg[2 * N];
int str[N][LOGN];
int coststr[N][LOGN];

inline void euler(int x)
{
    nivel[x] = ++niv;
    e[++ne] = x;
    poz[x] = ne;
    for(int i = lst[x]; i; i = urm[i])
    {
        euler(vf[i]);
        e[++ne] = x;
    }
    --niv;
}

inline int minim(int x, int y)
{
    return (nivel[x] < nivel[y]) ? x : y;
}

inline int minim2(int x, int y)
{
    return x < y ? x : y;
}

inline int drumMinim(int &x, int &y)
{
    int pozx = poz[x];
    int pozy = poz[y];
    if(pozx > pozy)
        swap(pozx, pozy);
    int l = lg[pozy - pozx + 1];
    int lca = minim(r[pozx][l], r[pozy - (1 << l) + 1][l]);
    int c1 = INF, c2 = INF;
    int xaux = x, yaux = y;
    int dif = nivel[x] - nivel[lca];
    int j = 0;
    while(dif != 0)
    {
        if(dif & 1)
        {
            c1 = minim2(c1, coststr[x][j]);
            x = str[x][j];
        }
        dif >>= 1;
        j++;
    }
    dif = nivel[y] - nivel[lca];
    j = 0;
    while(dif != 0)
    {
        if(dif & 1)
        {
            c2 = minim2(c2, coststr[y][j]);
            y = str[y][j];
        }
        dif >>= 1;
        j++;
    }
    x = xaux;
    y = yaux;
    int z = minim(c1, c2);
    xaux = (x * A + y * B) % n + 1;
    yaux = (y * C + z * D) % n + 1;
    x = xaux;
    y = yaux;
    return z;
}

int main()
{
    in >> n >> m >> p;

    for(int i = 2; i <= n; i++)
    {
        in >> t[i] >> cost[i];
        vf[++nvf] = i;
        urm[nvf] = lst[t[i]];
        lst[t[i]] = nvf;
    }
    in >> X >> Y >> A >> B >> C >> D;
    euler(1);
    for(int i = 2; i < 2 * N; i++)
        lg[i] = 1 + lg[i >> 1];
    for(int i = 1; i <= ne; i++)
        r[i][0] = e[i];
    for(int j = 1; j <= lg[ne]; j++)
        for(int i = 1; i <= ne; i++)
            if(i + (1 << (j - 1)) <= ne)
                r[i][j] = minim(r[i][j - 1], r[i + (1 << (j - 1))][j - 1]);
    for(int i = 2; i <= n; i++)
    {
        str[i][0] = t[i];
        coststr[i][0] = cost[i];
    }
    for(int j = 1; j <= lg[n]; j++)
        for(int i = 1; i <= n; i++)
        {
            str[i][j] = str[str[i][j - 1]][j - 1];
            coststr[i][j] = minim2(coststr[i][j - 1], coststr[str[i][j - 1]][j - 1]);
        }
    while(m--)
    {
        int z = drumMinim(X, Y);
        if(m < p)
            out << z << '\n';
    }
    return 0;
}