Cod sursa(job #933488)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 30 martie 2013 00:17:17
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

vector<pair<int,int> > v[32001];
int n,m,p,nre;
int f[3*32001], niv[3*32001], lg[3*32001],euler[3*32001],rmq[16][3*32001],t[3*32001][16],sol[3*32001][16];
bool used[32001];

void dfs(int nod, int nivel)
{
    used[nod] = true;
    euler[++nre] = nod;
    niv[nre] = nivel;
    f[nod] = nre;

    for(unsigned int i=0;i<v[nod].size();i++)
        if(!used[v[nod][i].first])
        {
            sol [0][ v[nod][i].first] = v[nod][i].second;
            t[0][ v[nod][i].first ] = nod;
            dfs(v[nod][i].first,nivel+1);
            euler[++nre] = nod;
            niv[nre] = nivel;
        }

}

int query(int nod, int dist)
{

    int r = 99999999;
    while(dist)
    {

        r = min(r, sol[lg[dist]][nod]);
        nod = t[lg[dist]][nod];
        dist-=(1<<lg[dist]);
    }
    return r;
}

//LCA

int LCA(int x, int y)
{
    int i = f[x];
    int j = f[y];
    if( i > j)
        swap(i,j);
    int k = lg[j-i+1];
    if( niv[ rmq[i][k]  ]  < niv[ rmq[j-(1<<k)+1][k]  ] );
        return euler[rmq[i][k]];
    return euler[rmq[j - (1<<k) + 1][k]];
}

int get_query(int X, int Y)
{
    if(X==Y)
            return 0;
    int nod = LCA(X,Y);
    int d1 = query( X, niv[f[X]] - niv[f[nod]]);
    int d2 =  query( Y,niv[f[Y]] - niv[f[nod]] );
    return  min(d1,d2);

}

int main()
{
    //citire
    int x,y;
    fin>>n>>m>>p;
    int nrn = n;
    for(int i=2;i<=n;i++)
    {
        fin>>x>>y;
        v[x].push_back(make_pair(i,y));
        v[i].push_back(make_pair(x,y));
    }


    dfs(1,0);

    //rmq
    n = nre;
    for(int i=1;i<=n;i++)
    {
        rmq[i][0] = i;
        if(i>1)
            lg[i] = lg[i>>1] + 1;
    }

    for(int k=1 ; (1<<k)<=n;k++)
        for(int i=1; i + (1<<k) - 1<=n;i++)
            if(niv[ rmq[i][k-1] ]  < niv[ rmq[i+(1<<(k-1))][k-1] ] )
                rmq[i][k] = rmq[i][k-1];
            else rmq[i][k] = rmq[i+(1<<(k-1))][k-1];

    for(int k=1; k<=lg[nrn];k++)
        for(int i=1;i<=nrn;i++)
        {
            t[k][i] = t[k-1][ t[k-1][i] ];
            sol[k][i] = min(sol[k-1][i], sol[k-1][t[k-1][i]]);
        }

    //queryuri
    int X,Y,A,B,C,D,Z;
    fin>>X>>Y>>A>>B>>C>>D;
    for(int i=1 ; i<=m ;i ++ )
    {
        Z = get_query(X,Y);
        if(i>=m-p+1)
            fout<<Z<<'\n';
        X = (X*A + Y*B)%nrn + 1;
        Y = (Y*C + Z*D)%nrn + 1;
    }

    fin.close();
    fout.close();
    return 0;
}