Cod sursa(job #927487)

Utilizator lily3Moldovan Liliana lily3 Data 25 martie 2013 20:26:39
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

int i,j,n,m,d[64001][15],x,y,A,B,C,D,Z,p,nr,prim[32001];
int lm,k,coloana[64001],tata[32001],min1,lca,c[32001];
bool viz[32001];
struct bombe
{
    int nod,cost;
};
vector<bombe> a[32001];
void df(int x)
{
    int i;
    viz[x]=1;
    d[++nr][0]=x;
    prim[x]=nr;
    for(i=0;i<a[x].size();++i)
    if(!viz[a[x][i].nod])
    {
        tata[a[x][i].nod]=x;
        c[a[x][i].nod]=a[x][i].cost;
        df(a[x][i].nod);
        d[++nr][0]=x;
    }
}
int stramos(int x,int y)
{
    int i,k,aux;
    if(prim[x]<prim[y])
    x=prim[x],y=prim[y];
    else
    aux=x,x=prim[y],y=prim[aux];

    k=coloana[y-x+1];
    lm=(y-x+1)-(1<<k);
    return min(d[x][k],d[x+lm][k]);

}
int main()
{
    ifstream f("atac.in");
    ofstream g("atac.out");
    f>>n>>m>>p;
    for(i=2;i<=n;++i)
    {
        f>>x>>y;
        a[x].push_back((bombe) {i,y});
        a[i].push_back((bombe) {x,y});
    }

    df(1);

    for(i=2;i<=nr;++i)
    coloana[i]=coloana[i/2]+1;

    for(i=1;(1<<i)<=nr;++i)
    {
        lm=nr-(1<<i)+1;
        k=1<<(i-1);
        for(j=1;j<=lm;++j)
        d[j][i]=min(d[j][i-1],d[j+k][i-1]);
    }

    f>>x>>y>>A>>B>>C>>D;
    /*while(m)
    {

        lca=stramos(x,y);

        int xx=x;
        Z=c[xx];
        while(tata[xx]!=lca)
        {
            xx=tata[xx];
            Z=min(Z,c[xx]);
        }

        xx=y;
        Z=min(Z,c[xx]);
        while(tata[xx]!=lca)
        {
            xx=tata[xx];
            Z=min(Z,c[xx]);
        }
        if(m<=p)
        g<<Z<<"\n";

        x=(A*x+B*y)%n+1;
        y=(C*y+D*Z)%n+1;

        --m;
    }*/

    return 0;
}