Cod sursa(job #929809)

Utilizator lily3Moldovan Liliana lily3 Data 27 martie 2013 11:51:33
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

long i,j,n,m,m1,m2,A,B,C,D,Z,nr,p;
long tata[32001],c[32001],niv[32001];
struct muchii
{
    int x,y,cost;
};
muchii a[32001];
bool cmp(muchii a,muchii b)
{
    return a.cost>b.cost;
}
void aflanivel(int x)
{
    if(tata[x]==x)
    return ;
    aflanivel(tata[x]);
    niv[x]=niv[tata[x]]+1;
}
int componenta(int x)
{
    while(x!=tata[x])
    x=tata[x];
    return x;
}
int main()
{
    ifstream f("atac.in");
    ofstream g("atac.out");
    f>>n>>m>>p;
    for(i=2;i<=n;++i)
    {
        f>>m1>>m2;
        a[i-1].x=m1;
        a[i-1].y=i;
        a[i-1].cost=m2;
        tata[i]=i;
    }
    tata[1]=1;
    sort(a+1,a+n,cmp);
    for(i=1;i<n;++i)
    {
        m1=componenta(a[i].x);
        m2=componenta(a[i].y);
        if(m1!=m2)
        {
            tata[m2]=m1;
            c[m2]=a[i].cost;
        }
    }

    for(i=1;i<=n;++i)
    if(!niv[i])
    aflanivel(i);

    f>>m1>>m2>>A>>B>>C>>D;

    while(m)
    {

        Z=1<<20;
        int xx=m1,yy=m2;
        while(niv[m1]>niv[m2])
        {
            Z=min(Z,c[m1]);
            m1=tata[m1];
        }
        while(niv[m2]>niv[m1])
        {
            Z=min(Z,c[m2]);
            m2=tata[m2];
        }
        while(m1!=m2)
        {
            Z=min(Z,min(c[m1],c[m2]));
            m1=tata[m1];
            m2=tata[m2];
        }

        if(Z==1<<20)
        Z=0;
        if(m<=p)
        g<<Z<<"\n";

        m1=(A*xx+B*yy)%n+1;
        m2=(C*yy+D*Z)%n+1;

        --m;
    }

    return 0;
}