Cod sursa(job #1096321)

Utilizator sebinechitasebi nechita sebinechita Data 1 februarie 2014 21:07:17
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define MAX 32100
int RMQ[2*MAX][18], par[MAX][17], stramosi[MAX][17], pa[MAX], dr, poz[MAX], nivel[MAX], viz[MAX], costpa[MAX], stiva[MAX], g, log[MAX*2];

vector <int> G[MAX];

int lca(int x, int y)
{
    if(x>y)
        swap(x, y);
    int g=log[y-x];
    if(nivel[RMQ[x][g]]<nivel[RMQ[y-(1<<g)+1][g]])
        return RMQ[x][g];
    return RMQ[y-(1<<g)+1][g];
}

int up(int nod)
{
    if(pa[nod])
       return up(pa[nod]);
    return nod;
}

void introdu(int nod, int depth)
{
    dr++;
    RMQ[dr][0]=nod;
    poz[nod]=dr;
    nivel[nod]=depth;
}

int euler(int nod, int depth)
{
    viz[nod]=1;
    introdu(nod, depth);
    for(int i=0;i<G[nod].size();i++)
    {
        if(!viz[G[nod][i]])
        {
            euler(G[nod][i], depth+1);
            introdu(nod, depth);
        }
    }
}

void dfs(int nod)
{
    stiva[++g]=nod;
    viz[nod]=0;
    int i;
    stramosi[nod][0]=pa[nod];
    for(i=1;(1<<i)<g;i++)
    {
        par[nod][i]=min(par[nod][i-1], par[stiva[g-(1<<(i-1))]][i-1]);
        stramosi[nod][i]=stramosi[g-(1<<(i-1))][i-1];
    }
    for(i=0;i<G[nod].size();i++)
    {
        if(viz[G[nod][i]])
        {
            dfs(G[nod][i]);
        }
    }
    --g;
}

int nr_bombe(int nod, int x)
{
    int rez=1<<29;
    int i;
    for(i=0;(1<<i)<=x;i++)
    {
        if(x&(1<<i))
        {
            rez=min(rez, par[nod][i]);
            nod=stramosi[nod][i];
        }
    }
    return rez;
}

int main()
{
    int n, m, p, i, u, v, l, j, X, Y, A, B, C, D, nod, Xp, Yp, Z;
    fin>>n;
    fin>>m>>p;
    for(i=2;i<=n;i++)
    {
        fin>>u>>v;
        G[u].push_back(i);
        pa[i]=u;
        par[i][0]=v;
    }


    l=up(1);
    euler(l, 0);
    for(i=2;i<=dr;i++)
    {
        log[i]=log[i/2]+1;
    }
    for(j=1;(1<<j)<=dr;j++)
    {
        for(i=1;i+(1<<(j-1))<=dr;i++)
        {
            if(nivel[RMQ[i][j-1]]<nivel[RMQ[i+(1<<(j-1))][j-1]])
                RMQ[i][j]=RMQ[i][j-1];
            else
                RMQ[i][j]=RMQ[i+(1<<(j-1))][j-1];
        }
    }
    dfs(l);
    fin>>X>>Y>>A>>B>>C>>D;

    while(m--)
    {
        //cout<<X<<" "<<Y<<" ";
        nod=lca(poz[X], poz[Y]);
        //cout<<nod<<" ";

        Z=min(nr_bombe(X, nivel[X]-nivel[nod]),nr_bombe(Y, nivel[Y]-nivel[nod]) );
        if(X==Y)
            Z=0;
        if(m<p)
            fout<<Z<<"\n";
        Xp=((X*A+Y*B)%n)+1;
        Yp=((Y*C+Z*D)%n)+1;
        X=Xp;
        Y=Yp;
    }

}