Cod sursa(job #1734333)

Utilizator ArambasaVlad Arambasa Arambasa Data 27 iulie 2016 06:49:45
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <iostream>
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
const int nmax=32000;
int rmq[18][4*nmax+5],level[nmax+5],dif,niv,n,m,p,U,val,i,k,first[nmax+5],a[18][nmax+5],lg[2*nmax+5],j,unu,doi,aa,b,ce,d,x,y,z,z1,z2,nod,drmin[18][nmax+5],drum,nr;
bitset<nmax+5> viz;
vector<int> v[nmax+5],c[nmax+5];
void dfs(int x,int lev)
{
    viz[x]=1;
    k++;
    level[x]=lev;
    rmq[0][k]=x;
    first[x]=k;
    for(int i=0;i<v[x].size();i++)
    {
        if(!viz[v[x][i]])
        {
            a[0][v[x][i]]=x;
            drmin[0][v[x][i]]=c[x][i];
            dfs(v[x][i],lev+1);
            k++;
            rmq[0][k]=x;
        }
    }
}
void buildrmq()
{
    for(i=1;(1<<i)<=k;i++)
        for(j=1;j<=k-(1<<i)+1;j++)
    {
        if(level[rmq[i-1][j]]<level[rmq[i-1][j+(1<<(i-1))]]) rmq[i][j]=rmq[i-1][j];
        else rmq[i][j]=rmq[i-1][j+(1<<(i-1))];
    }
}
int lca(int x,int y)
{
    unu=first[x];doi=first[y];
    if(unu>doi) swap(unu,doi);
    niv=lg[doi-unu+1];
    dif=doi-unu+1-(1<<niv);
   if(level[rmq[niv][unu]]<level[rmq[niv][unu+dif]]) return rmq[niv][unu];
   return rmq[niv][unu+dif];
}
void buildstructure()
{
    for(i=1;i<=lg[n];i++)
        for(j=1;j<=n;j++)
    {
        a[i][j]=a[i-1][a[i-1][j]];
        drmin[i][j]=min(drmin[i-1][j],drmin[i-1][a[i-1][j]]);
    }
}
int query(int x)
{
    nr=level[x]-level[nod];
    int j;int cpy=x;
    drum=(1<<30);
    while(nr!=0)
    {

        j=lg[((nr^(nr-1))&nr)];
        if(drmin[j][x]<drum)
            drum=drmin[j][x];
        nr-=(1<<j);
        x=a[j][x];
    }
    x=cpy;
    return drum;
}
int main()
{
    ifstream f("atac.in");
    ofstream g("atac.out");
    f>>n>>m>>p;
    for(i=2;i<=n;i++)
    {
        f>>U>>val;
        v[i].push_back(U);
        c[i].push_back(val);
        v[U].push_back(i);
        c[U].push_back(val);
    }
    dfs(1,1);
    for(i=2;i<=k;i++)
        lg[i]=lg[i/2]+1;
    f>>x>>y>>aa>>b>>ce>>d;
        z=0;
    buildrmq();
    buildstructure();
    for(i=1;i<=m;i++)
    {
        nod=lca(x,y);
        z1=query(x);
        z2=query(y);
        z=min(z1,z2);
        if(x==y) z=0;
        if(i>=m-p+1) g<<z<<'\n';
        x=(x*aa+y*b)%n+1;
        y=(y*ce+z*d)%n+1;
    }
    return 0;
}