Cod sursa(job #933509)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 30 martie 2013 00:37:48
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
//sursa mihaivisuian, test pt kbs

#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");

int t[16][32001],cst[16][32001],log[3*32001],rmq[3*32001][16],niv[3*32001],first[32001],euler[3*32001];
int n,m,p,x,y,a,b,c,d,z,nr;
vector<pair<int,int> >g[32001];
bool vis[32001];
void Dfs(int x, int lvl)
{
    vis[x]=true;
    euler[++nr]=x;
    first[x]=nr;
    niv[nr]=lvl;
    for(vector<pair<int,int> >::iterator it=g[x].begin(); it<g[x].end(); it++)
    {
        if(!vis[it->first])
        {
            t[0][it->first]=x;
            cst[0][it->first]=it->second;
            Dfs(it->first,lvl+1);
            euler[++nr]=x;
            niv[nr]=lvl;
        }
    }
}
int Lca(int x, int y)
{
    x=first[x],y=first[y];
    if(x>y) swap(x,y);
    int l=log[y-x+1];
    if(niv[rmq[x][l]]<niv[rmq[y-(1<<l)+1][l]])
        return euler[rmq[x][l]];
    return euler[rmq[y-(1<<l)+1][l]];
}
int GetRes(int nod, int dist)
{
    int res = 999999;
    while(dist)
    {
        res = min(res,cst[log[dist]][nod]);
        nod=t[log[dist]][nod];
        dist-=(1<<log[dist]);
    }
    return res;
}
 int Query(int x, int y)
{
    if(x==y) return 0;
    int nod= Lca(x,y);
    int road1 = GetRes(x,niv[first[x]]-niv[first[nod]]);
    int road2 = GetRes(y,niv[first[y]]-niv[first[nod]]);
    return min(road1,road2);
}
int main()
{
    fin>>n>>m>>p;
    for(int i = 2; i<= n; i++ )
    {
        fin>>x>>c;
        g[x].push_back(make_pair(i,c));
        g[i].push_back(make_pair(x,c));
    }
    fin>>x>>y>>a>>b>>c>>d;
    Dfs(1,0);
    for(int i = 1; i<= nr; i++ )
    {
        rmq[i][0]=i;
        if(i>1) log[i]=1+log[i>>1];
    }
    for(int j = 1; (1<<j)<= nr; j++ )
        for(int i = 1; i +(1<<j)-1 <= nr; i++ )
            if(niv[rmq[i][j-1]] < niv[rmq[i+(1<<(j-1))][j-1]])
                rmq[i][j]=rmq[i][j-1];
            else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
    for(int i = 1; i <= log[n]; i++ )
    {
        for(int j = 1; j<= n; j++ )
        {
            t[i][j]=t[i-1][t[i-1][j]];
            cst[i][j]=min(cst[i-1][j],cst[i-1][t[i-1][j]]);
        }
    }
    while(m>p)
    {
        z = Query(x,y);
        x=(a*x+y*b)%n+1;
        y=(y*c+z*d)%n+1;
        m--;
    }
    while(m)
    {
        m--;
        int sol = Query(x,y);
        x=(a*x+b*y)%n+1;
        y=(y*c+sol*d)%n+1;
        fout<<sol<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}