Cod sursa(job #1385620)

Utilizator taigi100Cazacu Robert taigi100 Data 12 martie 2015 09:49:33
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
/*
    Keep It Simple!
*/

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second

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

const int kMaxN = 32005;
const int kInf = 0x3f3f3f3f;

typedef pair<int,int> pii;

long long N,M,P,X,Y,A,B,C,D;
vector<pii> G[kMaxN];
int lb[kMaxN];
pii dp[20][kMaxN],t[kMaxN];
int euler[kMaxN],lvl[kMaxN],first[kMaxN];
int ultim,rmq[20][kMaxN];

void ComputeLb() // ok
{
    lb[1] = 0;
    for(int i=2;i < kMaxN; ++i)
        lb[i] = lb[i>>1] + 1;
}

void ReadInput() // ok
{
    fin >> N >> M >> P;
    int x,y;
    for(int i=2; i<=N; ++i)
    {
        fin >> x >> y;
        G[i].pb(mp(x,y));
        G[x].pb(mp(i,y));
    }
    fin >> X >> Y >> A >> B >> C >> D;
}

void ComputeDpNdRmq()
{
    for(int i=1; i<=N; ++i)
        for(int j=1; (1<<j) <= N; ++j)
            dp[j][i].fi = -1;

    for(int i=1; i<=N; ++i)
           dp[0][i] = t[i];
    for(int i=1; i<=ultim; ++i)
            rmq[0][i] = i;

    for(int i=1; (1<<i) <=N; ++i)
        for(int j=1; j<=N; ++j)
            if(dp[i-1][j].fi != -1)
            {
                dp[i][j].fi = dp[i-1][dp[i-1][j].fi].fi;
                dp[i][j].se = min(dp[i-1][dp[i-1][j].fi].se,dp[i-1][j].se);
            }

    for(int i=1; (1<<i)<ultim; ++i)
        for(int j=1; j <= ultim - (1<<i); ++j)
        {
                int len = 1 << (i-1);
                rmq[i][j] = rmq[i-1][j];
                if(lvl[rmq[i][j]] > lvl[rmq[i-1][j+len]])
                    rmq[i][j] = rmq[i-1][j+len];
        }
}

void ComputeDFS(int node,int level) // ok
{
    euler[++ultim] = node;
    lvl[ultim] = node;
    first[node] = ultim;

    for(auto it:G[node])
        if(t[it.fi].fi != node)
        {
            t[it.fi].fi = node;
            t[it.fi].se = it.se;

            ComputeDFS(it.fi,level+1);

            euler[++ultim] = node;
            lvl[ultim] = level;
        }
}

int GetLCA(int x,int y)
{
    int a = first[x], b = first[y];
    if( a > b ) swap(a,b);

    //find LCA
    int diff = (b-a+1);
    int lg = lb[diff];
    int sh = diff - (1<<lg);
    int ans = rmq[lg][a];
    if(lvl[rmq[lg][a]] > lvl[rmq[lg][a+sh]])
        ans = rmq[lg][a+sh];
    return euler[ans];
}

int query(int x,int y)
{
    if(x == y) return 0;
    int Lc = GetLCA(x,y);
    int ans = kInf;

    for(int idx = lb[lvl[first[x]]]; idx; --idx)
        if(lvl[first[x]] - (1<<idx) >= lvl[first[Lc]])
        {
            ans = min(ans,dp[idx][x].se);
            x = dp[idx][x].fi;
        }

    for(int idx = lb[lvl[first[y]]]; idx; --idx)
        if(lvl[first[y]] - (1<<idx) >= lvl[first[Lc]])
        {
            ans = min(ans,dp[idx][y].se);
            y = dp[idx][y].fi;
        }

    return ans;
}

void Solve() // ok
{
    ComputeLb();
    ReadInput();
    ComputeDFS(1,0);
    ComputeDpNdRmq();

    while(M)
    {
        int Z = query(X,Y);
        if(M<=P)
            fout << Z << '\n';

        X = (X*A + Y*B) % (N+1);
        Y = (Y*C + Z*D) % (N+1);
        --M;
    }
}

int main() // ok
{
    Solve();
    return 0;
}