Pagini recente » Cod sursa (job #1871382) | Cod sursa (job #1046006) | Cod sursa (job #1267735) | Cod sursa (job #2418318) | Cod sursa (job #1154713)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int MAX_N = 32000;
int n, m, p, x, y, a, b, c, d, niv;
int minim[16][MAX_N+1], t[16][MAX_N+1], bombe[16][MAX_N+1], nivel[MAX_N+1];
int logn;
vector<int> vecini[MAX_N+1];
int log2(int x)
{
if(x == 1)
{
return 0;
}
int nr = 0;
while(x != 1)
{
x /= 2;
nr++;
}
return nr;
}
void dfs(int tata)
{
int i, fiu;
//euler[1][++nr] = tata;
//poz[tata] = nr;
for(i = 0;i < vecini[tata].size(); i++)
{
fiu = vecini[tata][i];
nivel[fiu] = ++niv;
dfs(fiu);
//euler[1][++nr] = tata;
}
}
int min(int a, int b)
{
return (a < b) ? a:b;
}
int bsearch(int a, int b)
{
int pas = logn;
while(pas != 0)
{
if(nivel[t[pas][a]] >= nivel[b])
{
a = t[pas][a];
}
pas--;
}
return a;
}
int binaryLCA(int x, int y)
{
int pas = logn;
while(pas != 0)
{
if(t[pas][x] != t[pas][y])
{
x = t[pas][x];
y = t[pas][y];
}
pas--;
}
return x;
}
int main()
{
int i, j, rez;
in >> n >> m >> p;
for(i = 2; i <= n; i++)
{
in >> t[0][i] >> bombe[0][i];
vecini[t[0][i]].push_back(i);
}
logn = log2(n);
for(i = 1; i <= logn; i++)
{
for(j = 1; j <= n; j++)
{
t[i][j] = t[i-1][t[i-1][j]];
}
}
for(j = 1; j <= n; j++)
{
minim[0][j] = bombe[0][j];
}
for(i = 1; i <= logn; i++)
{
for(j = 1; j <= n; j++)
{
minim[i][j] = min(minim[i-1][j], minim[i-1][t[i-1][j]]);
}
}
in >> x >> y >> a >> b >> c >> d;
int xprim, yprim;
for(i = 1; i <= m; i++)
{
xprim = x;
yprim = y;
if(nivel[x] > nivel[y])
{
xprim = bsearch(x, y);
} else if(nivel[x] < nivel[y])
{
yprim = bsearch(y, x);
}
rez = minim[0][binaryLCA(xprim, yprim)];
if(i > m-p)
{
out << rez << "\n";
}
x = (x*a + y*b)%n + 1;
y = (y*c + rez*d)%n + 1;
}
return 0;
}