Cod sursa(job #974491)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 17 iulie 2013 13:01:18
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define newn a[x][i].second
#define cost a[x][i].first;

using namespace std;

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

const int N = 32010;
const int E = N * 2;
const int L = 17;

int n, m, p, nr, A, B, C, D, X, Y, Z, t[L][N], dp[L][N],
first[N], euler[E], height[E], lg[E], rmq[L][E];
typedef pair <int, int> nod;
vector <nod> a[N];

void dfs(int x, int level)
{
    ++nr;
    euler[nr] = x;
    height[nr] = level;
    first[x] = nr;
    for(unsigned i=0; i<a[x].size(); i++)
        {
            dfs(newn, level+1);
            ++nr;
            euler[nr] = x;
            height[nr] = level;
        }
}

void Rmq()
{
    for(int i=2; i<=nr; i++)
        lg[i] = lg[i>>1] + 1;
    for(int i=1; i<=nr; i++)
        rmq[0][i] = i;

    for(int i=1; (1<<i) <= nr; i++)
        for(int j=1; j <= nr - (1<<i); j++)
        {
            const int l = 1 << (i-1);
            rmq[i][j] = rmq[i-1][j];
            if(height[rmq[i][j]] > height[rmq[i-1][j+l]])
                rmq[i][j] = rmq[i-1][j+l];
        }
}

int LCA(int x, int y)
{
    x = first[x], y = first[y];
    if(x > y) swap(x, y);

    const int l = lg[y-x+1];
    int poz = rmq[l][x];
    if(height[poz] > height[rmq[l][y-(1<<l)+1]])
        poz = rmq[l][y-(1<<l)+1];
    return poz;
}

void Ancestor()
{
    for(int i=1; (1<<i) <= n; i++)
        for(int j=1; j<=n; j++)
        {
            t[i][j] = t[i-1][t[i-1][j]];
            dp[i][j] = min(dp[i-1][j], dp[i-1][t[i-1][j]]);
        }
}

int Compute(int nod, int lca)
{
    int rez = (1 << 25);
    int depth = height[first[nod]] - height[first[lca]];

    while(depth)
    {
        rez = min(rez, dp[lg[depth]][nod]);
        nod = t[lg[depth]][nod];
        depth -= (1 << lg[depth]);
    }
    return rez;
}

int Query(int x, int y)
{
    if(x == y) return 0;
    int lca = euler[LCA(X, Y)];
    int drum1 = Compute(x, lca);
    int drum2 = Compute(y, lca);
    return min(drum1, drum2);
}

int main()
{
    fin>>n>>m>>p;
    for(int i=2; i<=n; i++)
    {
        fin>>t[0][i]>>dp[0][i];
        a[t[0][i]].push_back(nod(dp[0][i], i));
    }
    fin>>X>>Y>>A>>B>>C>>D;

    dfs(1, 0);
    Rmq();
    Ancestor();
    while(m--)
    {
            Z = Query(X, Y);
            X = (X*A + Y*B) % n + 1;
            Y = (Y*C + Z*D) % n + 1;
            if(m < p) fout<<Z<<'\n';
    }
    return 0;
}