Cod sursa(job #1692161)

Utilizator marioviperconstantin mario marioviper Data 20 aprilie 2016 12:09:26
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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;}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;
}
ifstream f("atac.in");
ofstream g("atac.out");
int main(){
    f>>n>>m>>k;
    for(i=2;i<=n;++i){
     a[i-1].x=i;
     f>>a[i-1].y>>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[m1]=m2;
       c[m1]=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=1048576;
        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(min1==1048576){min1=0;}
        if(m<k){g<<min1<<'\n';}
        m1=(x*A+y*B)%n+1;
        m2=(y*C+min1*D)%n+1;
    }
}