Cod sursa(job #1385534)

Utilizator taigi100Cazacu Robert taigi100 Data 12 martie 2015 01:07:23
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
/*
    Keep It Simple!
*/

#include <fstream>
#include <vector>
#include <list>
#include <stack>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

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

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

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

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

int lb[kMaxN],lvl[2*kMaxN+100],euler[2*kMaxN+100],first[kMaxN];
ll n,m,p,ans,ultim;
ll x,y,a,b,c,d;

int rmq[16][kMaxN];

struct el
{
    ll a,b;
}dp[16][kMaxN],t[kMaxN];

vector<pii> G[kMaxN];

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

void DFS(int node,int level)
{
    euler[++ultim] = node;
    lvl[ultim] = level;
    first[node] = ultim;
    for(auto vecin : G[node])
        if(!t[vecin.fi].a)
        {
            t[vecin.fi].a = node;
            t[vecin.fi].b = vecin.se;
            DFS(vecin.fi,level+1);
            euler[++ultim] = node;
            lvl[ultim] = level;
        }

}

void ComputeDads()
{
    t[1].a = -1;
    DFS(1,0);
}

void ComputeLCA()
{
    for(int i=1; i<=n; ++i)
        for(int j=1; 1<<j <=n; ++j)
            dp[j][i].a = -1;

    for(int i=1; i<=n; ++i)
        dp[0][i] = t[i];

    for(int i=1; 1<<i <=n; ++i)
        for(int j=1; j<=n; ++j)
        {
            dp[i][j].a = dp[i-1][dp[i-1][j].a].a;
            dp[i][j].b = min(dp[i-1][dp[i-1][j].a].b,dp[i-1][j].b);
        }
}

void ComputeRMQ()
{
    for(int i=1; i<=ultim; ++i)
        rmq[0][i] = i;

    for(int i=1; (1<<i) < ultim; ++i)
        for(int j=1; j <= ultim - (1<<i); ++j)
        {
            int pw = 1 << (i - 1);

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

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

    int lg = lb[b-a+1];
    ans = rmq[lg][a];
    int sh = (b-a+1) - ( 1 << lg );
    if(lvl[ans] > 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 = LCA(x,y);
    ans = kInf;

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

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

    return ans;
}

void Solve()
{
    fin >> n >> m >> p;
    for(int i=2;i<=n;++i)
    {
        fin >> x >> y;
        G[x].pb(mp(i,y));
        G[i].pb(mp(x,y));
    }
    fin >> x >> y >> a >> b >> c >> d;

    ComputeLb();
    ComputeDads();
    ComputeLCA();
    ComputeRMQ();

    int z; ++m;
    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';
        --m;
    }
}

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