Cod sursa(job #1585694)

Utilizator feli2felicia iuga feli2 Data 31 ianuarie 2016 12:56:24
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>

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

vector <pair<int, int> > G[32005];

int fir[32005], in, rmq[18][32005*2+1], log[32005*2+1], i, n, m, p, u, v, j, x, y, fx, fy, z, a, b, c, d, r;
bool viz[32005];

void dfs(int node)
{
    viz[node]=1;
    for(int i=0;i<G[node].size();i++)
    {
        if(!viz[G[node][i].first])
        {
            in++;
            if(!fir[G[node][i].first])
                fir[G[node][i].first]=in+1;
            rmq[0][in]=G[node][i].second;
            dfs(G[node][i].first);
            rmq[0][++in]=G[node][i].second;
        }
    }
    /*if(G[node].size()==1)
        in--;*/
}

int query(int x, int y)
{
    int dist=y-x;
    int put=log[dist];
    if((1<<put)==dist)
    {
        return rmq[put][x];
    }
    else
        return min(rmq[put][x],rmq[put][y-(1<<put)+1]);
}

int main()
{
    fin>>n>>m>>p;
    for(i=2;i<=n;i++)
    {
        fin>>u>>v;
        G[i].push_back(make_pair(u,v));
        G[u].push_back(make_pair(i,v));
    }
    in=0;
    fir[1]=1;
    dfs(1);
    for(i=2;i<in;i++)
        log[i]=log[i/2]+1;
    for(i=1;(1<<i)<in;i++)
    {
        for(j=1;j+(1<<i)-1<in;j++)
        {
            rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
        }
    }
    fin>>x>>y>>a>>b>>c>>d;
    r=m;
    for(i=1;i<=m;i++)
    {
        if(x!=y)
        {
            fx=fir[x];
            fy=fir[y];
            if(fx>fy)
                swap(fx,fy);
            z=query(fx,fy);
        }
        else
        {
            z=0;
        }
        if(r<=p)
        {
            fout<<z<<'\n';
        }
        r--;
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    in=0;
    return 0;
}