Cod sursa(job #1590172)

Utilizator feli2felicia iuga feli2 Data 4 februarie 2016 19:19:49
Problema Atac Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#define f first
#define s second

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

vector <pair<int,int> > G[32005];
int level[32005], str[20][32005], mn[20][32005], lv, lvmx, i, j, n, minn, m, p, u, v, lg[32005], a, b, c, d, cx, cy, put, x1, x2, z, x, y;
bool viz[32005];

void dfs(int node)
{
    level[node]=lv;
    if(lv>lvmx)
        lvmx=lv;
    viz[node]=1;
    for(int i=0;i<G[node].size();i++)
    {
        if(!viz[G[node][i].f])
        {
            str[0][G[node][i].f]=node;
            mn[0][G[node][i].f]=G[node][i].s;
            lv++;
            dfs(G[node][i].f);
            lv--;
        }
    }
}

void fa_str()
{
    for(i=1;(1<<i)<=lvmx;i++)
    {
        for(j=1;j<=n;j++)
        {
            str[i][j]=str[i-1][str[i-1][j]];
            mn[i][j]=min(mn[i-1][j],mn[i-1][str[i-1][j]]);
        }
    }
}

int str_query(int node, int p)
{
    int i=0;
    while((1<<i)<=p)
    {
        if((1<<i)&p)
        {
            if(mn[i][node]<minn)
                minn=mn[i][node];
            node=str[i][node];
        }
        i++;
    }
    return node;
}

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));
    }
    lv=1;
    dfs(1);
    for(i=2;i<=lvmx;i++)
        lg[i]=lg[i/2]+1;
    fin>>x>>y>>a>>b>>c>>d;
    fa_str();
    for(i=1;i<=m-p;i++)
    {
        if(x!=y)
        {
            cx=x;
            cy=y;
            minn=100005;
            if(level[x]>level[y])
            {
                cx=str_query(cx,level[x]-level[y]);
            }
            if(level[y]>level[x])
            {
                cy=str_query(cy,level[y]-level[x]);
            }
            put=lg[lvmx];
            while(str[0][cx]!=str[0][cy])
            {
                x1=str[put][cx];
                x2=str[put][cy];
                if(x1!=x2)
                {
                    if(minn>mn[put][cx])
                        minn=mn[put][cx];
                    if(minn>mn[put][cy])
                        minn=mn[put][cy];
                    cx=x1;
                    cy=x2;
                }
                put--;
            }
            if(minn>mn[0][cx])
                minn=mn[0][cx];
            if(minn>mn[put][cy])
                minn=mn[put][cy];
            z=minn;
        }
        else
            z=0;
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
    }
    for(i=1;i<=p;i++)
    {
        if(x!=y)
        {
            cx=x;
            cy=y;
            minn=100005;
            if(level[x]>level[y])
            {
                cx=str_query(cx,level[x]-level[y]);
            }
            if(level[y]>level[x])
            {
                cy=str_query(cy,level[y]-level[x]);
            }
            if(cx!=cy)
            {
                put=lg[lvmx];
                while(str[0][cx]!=str[0][cy])
                {
                    x1=str[put][cx];
                    x2=str[put][cy];
                    if(x1!=x2)
                    {
                        if(minn>mn[put][cx])
                            minn=mn[put][cx];
                        if(minn>mn[put][cy])
                            minn=mn[put][cy];
                        cx=x1;
                        cy=x2;
                    }
                    put--;
                }
                if(minn>mn[0][cx])
                    minn=mn[0][cx];
                if(minn>mn[0][cy])
                    minn=mn[0][cy];
            }
            z=minn;
        }
        else
            z=0;
        x=(x*a+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        fout<<z<<'\n';
    }
    return 0;
}