Cod sursa(job #1585746)

Utilizator feli2felicia iuga feli2 Data 31 ianuarie 2016 13:52:08
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

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

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

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

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

int query(int x, int y)
{
    int dist=y-x;
    int put=lg[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].push_back(1);
    dfs(1);
    fir[1].push_back(in);
    for(i=2;i<in;i++)
        lg[i]=lg[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)
        {
            mn=in;
            for(i1=0;i1<fir[x].size();i1++)
            {
                for(i2=0;i2<fir[y].size();i2++)
                {
                    if(abs(fir[x][i1]-fir[y][i2])<mn)
                    {
                        mn=abs(fir[x][i1]-fir[y][i2]);
                        fx=fir[x][i1];
                        fy=fir[y][i2];
                    }
                }
            }
            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;
    }
    return 0;
}