Cod sursa(job #1385527)

Utilizator taigi100Cazacu Robert taigi100 Data 12 martie 2015 00:33:57
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 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[kMaxN];
ll n,m,p,ans;
ll x,y,a,b,c,d;

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)
{
    for(auto vecin : G[node])
        if(!t[vecin.fi].a)
        {
            t[vecin.fi].a = node;
            t[vecin.fi].b = vecin.se;
            lvl[vecin.fi] = lvl[node] + 1;
            DFS(vecin.fi);
        }
}

void ComputeDads()
{
    DFS(1);
}

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);
        }
}

int Query(int x,int y)
{
    ans = kInf;
    if( x == y ) return 0;
    if(lvl[x] < lvl[y])
        swap(x,y);

    // get x to the same lvl as y.
    for(int i = lb[lvl[x]]; i; --i)
        if(lvl[x] - (1<<i) >= lvl[y])
        {
            ans = min(ans,dp[i][x].b);
            x = dp[i][x].a;
        }
    // if we made it nigga.
    if(x == y)
        return ans;

    //we gonna make it nigga.
    for(int i = lb[lvl[x]]; i; --i)
        if(dp[i][x].a != -1 && dp[i][x].a != dp[i][y].a)
        {
            ans = min(ans,min(dp[i][x].b,dp[i][y].b));
            x = dp[i][x].a,y = dp[i][y].a;
        }

    // yep, made it.
    ans = min(ans,t[x].b);
    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();

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