Cod sursa(job #1254908)

Utilizator misinozzz zzz misino Data 3 noiembrie 2014 18:21:42
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include<fstream>
#include<vector>

#define N 32100
#define M 17
#define INF 0x3f3f3f3f

using namespace std;

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

int n,m,sol,P,dif,l,i,j,lc,x,y,k,a,b,c,d,e[N * 2],logg[N * 2],niv[N * 2],nivnod[N],p[N],cost[M][N],t[M][N],rmq[M + 1][N * 2];

vector<int>v[N];

inline void dfs(int x,int nivel){
    e[++k] = x;
    niv[k] = nivel;
    nivnod[x] = nivel;
    p[x] = k;

    for(vector<int>::iterator it = v[x].begin(); it != v[x].end(); ++it)
    {
        dfs(*it, nivel + 1);

        e[++k] = x;
        niv[k] = nivel;
    }
}

inline void RMQ(){
    for(i = 2; i <= k; ++i)
        logg[i] = logg[i >> 1] + 1;

    for(i = 1; i <= k; ++i)
        rmq[0][i] = i;

    for(i = 1; (1 << i) <= k; ++i)
        for(j = 1; j + (1 << (i - 1)) <= k; ++j)
        {
            rmq[i][j] = rmq[i - 1][j];

            if(niv[rmq[i - 1][j + (1 << (i - 1))]] < niv[rmq[i][j]])
                rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
        }

    for(i = 1; (1 << i) <= n; ++i)
        for(j = 1; j <= n; ++j)
            t[i][j] = t[i - 1][t[i - 1][j]],
            cost[i][j] = min(cost[i - 1][j], cost[i - 1][t[i - 1][j]]);
}

inline int LCA(int x,int y){
    x = p[x];
    y = p[y];

    if(x > y)
        swap(x, y);

    int dif,l,sol,poz;

    dif = y - x + 1;
    l = logg[dif];
    poz = dif - (1 << l);

    sol = rmq[l][x];

    if(niv[sol] > niv[rmq[l][x + poz]])
        sol = rmq[l][x + poz];

    return e[sol];
}

inline int rez(int x,int tata){
    dif = nivnod[x] - nivnod[tata];
    l = logg[dif];
    int rez = INF;

    for(int i = 0; i <= l; ++i)
        if(dif & (1 << i))
        {
            rez = min(rez, cost[i][x]);
            x = t[i][x];
        }

    return rez;
}

int main()
{
    f >> n >> m >> P;

    for(i = 2; i <= n; ++i)
    {
        f >> x >> y;

        v[x].push_back(i);

        cost[0][i] = y;
        t[0][i] = x;
    }

    dfs(1, 0);
    RMQ();

    f >> x >> y >> a >> b >> c >> d;

    for(i = 1; i <= m; ++i)
    {
        lc = LCA(x, y);

        sol = min(rez(x, lc), rez(y, lc));

        if(x == y)
            sol = 0;

        if(i > m - P)
            g << sol << '\n';

        x = (1LL * x * a + 1LL * y * b) % n + 1;
        y = (1LL * y * c + 1LL * sol * d) % n + 1;
    }

    return 0;
}