Cod sursa(job #930717)

Utilizator valentina506Moraru Valentina valentina506 Data 27 martie 2013 19:48:56
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m,i,j,k,tata[32001],c[32001],min1,niv[32001],m1,m2,A,B,C,D,x,y,nr;
struct muchie
{
    int x,y,cost;
};
muchie a[32001];
int detniv(int x)
{
    if(x==tata[x])
    return 0;
    detniv(tata[x]);
    niv[x]=niv[ tata[x] ]+1;
}
int det(int x)
{
    while(x!=tata[x])
    x=tata[x];
    return x;
}
bool cmp(muchie a, muchie b)
{
    return a.cost>b.cost;
}
int main()
{
    ifstream f("atac.in");
    ofstream g("atac.out");
    f>>n>>m>>k;
    for(i=2;i<=n;++i)
    {
        a[i-1].y=i;
        f>>a[i-1].x>>a[i-1].cost;
    }
    for(i=1;i<=n;++i)
    tata[i]=i;
    sort(a+1,a+n,cmp);
    for(i=1;i<n;++i)
    {
        m1=det(a[i].x);
        m2=det(a[i].y);
        if(m1!=m2)
        {tata[m2]=m1;
        c[m2]=a[i].cost;}
    }

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

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

    while(m--)
    {
        x=m1;
        y=m2;
        min1=1<<20;
        while(niv[m1]>niv[m2])
        {
            min1=min(min1,c[m1]);
            m1=tata[m1];
        }

        while(niv[m2]>niv[m1])
        {
            min1=min(min1,c[m2]);
            m2=tata[m2];
        }

        while(m1!=m2)
        {
            min1=min(min1,min(c[m1],c[m2]));
            m1=tata[m1];
            m2=tata[m2];
        }

        if(m<k)
        g<<min1<<'\n';

        m1=(x*A+y*B)%n+1;
        m2=(y*C+min1*D)%n+1;

    }

}