Pagini recente » Cod sursa (job #587721) | Cod sursa (job #2681547) | Cod sursa (job #3191857) | Cod sursa (job #2116591) | Cod sursa (job #15)
Cod sursa(job #15)
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int euler[200001];
int adancimi[200001];
int poz[200001];
int min[200000][25];
int minpos[200000][25];
int cost[32001];
int tata[32001];
int bif[33000];
int n , i , j , x , y , q ;
int m , p;
int a[32000][100], ind;
long opt[1000][1000];
int stiva[33001];
int stramosi[33000][16];
int coststr[33000][16];
int k ;
int aux , eu;
int kk;
int X,Y,A,B,C,D,Z , var , minim;
long doi[20];
struct xy
{
int x , y;
};
xy sir[32001];
int www;
int lca(int a , int b)
{
kk = 0;
www = b - a + 1;
while(www)
{
www>>=1;
kk++;
}
// kk = www&(www^(www-1));
if (doi[kk]>b-a+1)
kk--;
// kk++;
k = doi[kk];
if ( min[a][kk] <= min[b-k+1][kk])
return euler[minpos[a][kk]];
else
return euler[minpos[b-k+1][kk]];
}
void df(int nod)
{
bif[nod] = 1;
stiva[0]++;
stiva[stiva[0]] = nod;
eu++;
euler[eu] = stiva[stiva[0]];
adancimi[eu] = stiva[0];
ind = 0;
for (int q = 1 ; q <= a[nod][0];q++)
{
if (bif[a[nod][q]]==0)
{
ind = 1;
bif[a[nod][q]] = 1;
tata[a[nod][q]] = nod;
df(a[nod][q]);
}
}
if (ind==0)
{
stiva[0]--;
eu++;
euler[eu] = stiva[stiva[0]];
adancimi[eu] = stiva[0];
}
}
int main()
{
freopen("atac.in","r",stdin);
freopen("atac2.out","w",stdout);
doi[0] = 1;
doi[1]=2;doi[2]=4;doi[3]=8;doi[4]=16;doi[5]=32;doi[6]=64;doi[7]=128;doi[8]=256;doi[9]=512;doi[10]=1024;doi[11]=2048;doi[12]=4096;doi[13]=8192;doi[14]=16384;doi[15]=32768;doi[16]=65536;doi[17]=131072;doi[18]=262144;
scanf("%d%d%d",&n,&m,&p);
for (i = 1 ; i < n ; i++)
{
scanf("%d %d",&sir[i].x,&sir[i].y);
a[sir[i].x][0]++;
a[sir[i].x][a[sir[i].x][0]] = i+1;
a[i+1][0]++;
a[i+1][a[i+1][0]] = sir[i].x;
}
df(1);
for (i = 1 ; i < n ; i++)
{
if (tata[i+1]==sir[i].x)
cost[i+1] = sir[i].y;
if (tata[sir[i].x]==i+1)
cost[sir[i].x] = i+1;
}
for (i = 1 ; i < eu ; i++)
poz[euler[i]] = i;
aux = eu;
while(aux)
{
k++;
aux>>=1;
}
if (doi[k] > eu)
k--;
for (i = 1 ; i < eu ; i++)
{
min[i][0] = adancimi[i];
minpos[i][0] = i;
}
for (i = 1 ; i <= k ; i++)
{
for (j = 1 ; j < eu ; j++)
{
if (j+doi[i-1] < eu)
{
kk = doi[i-1];
if ( min[j][i-1] < min[j+kk][i-1])
{
min[j][i] = min[j][i-1];
minpos[j][i] = minpos[j][i-1];
}
else
{
min[j][i] = min[j+kk][i-1];
minpos[j][i] = minpos[j+kk][i-1];
}
}
else
{
min[j][i] = min[j][i-1];
minpos[j][i] = minpos[j][i-1];
}
}
}
scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
for (i = 1 ; i <= m ; i++)
{
if (poz[Y]>poz[X])
var = lca(poz[X],poz[Y]);
else
var = lca(poz[Y],poz[X]);
if (tata[X]==Y)
var = Y;
if (tata[Y]==X)
var = X;
if (X==1 || Y == 1)
var = 1;
minim = 200000;
if (X!=1&& X != var && X != Y)
{
aux = X;
if (cost[aux] < minim)
minim = cost[aux];
while(tata[aux]!=var && tata[aux]!=0)
{
if (cost[aux]<minim)
minim = cost[aux];
aux = tata[aux];
}
if (cost[aux]<minim)
minim = cost[aux];
}
if (Y!=1 && Y != var && X!=Y)
{
aux = Y;
if (cost[aux] < minim)
minim = cost[aux];
while(tata[aux]!=var&&tata[aux]!=0)
{
if (cost[aux]<minim)
minim = cost[aux];
aux = tata[aux];
}
if (cost[aux]<minim)
minim = cost[aux];
}
if (minim==200000)
minim = 0;
// printf("%d %ld\n",X,Y);
if ( i >= m-p+1)
{
if (X==Y)
{
minim = 0;
printf("%d\n",minim);
}
else
if (tata[Y]==X)
{
minim = cost[Y];
printf("%d\n",cost[Y]);
}
else
if (tata[X]==Y)
{
minim = cost[X];
printf("%d\n",cost[X]);
}
else
{
printf("%d\n",minim);
}
}
X = (X*A + Y*B)%n+1;
Y = (Y*C + minim*D)%n+1;
}
// printf("%d ",lca(poz[352],poz[307]));
return 0;
}