Pagini recente » Cod sursa (job #1836018) | Cod sursa (job #3269014) | Cod sursa (job #112439) | Cod sursa (job #683681) | Cod sursa (job #2789367)
#include <fstream>
#include <vector>
#include <climits>
using namespace std;
const int NMAX = 32000;
const int LOGMAX = 14;
int n;
vector<pair<int, int>> graf[1 + NMAX];
bool vizitat[1 + NMAX];
pair<int, int> minimeLog[1 + LOGMAX][1 + NMAX];
int h[1 + NMAX];
vector<int> liniarizare;
int primaAparitie[1 + NMAX];
int putere2Max[1 + 2 * NMAX - 1];
pair<int, int> rmq[1 + 2 * NMAX - 1][1 + LOGMAX];
vector<int> sol;
void dfs(int nod, int t, int c, int adanc)
{
vizitat[nod] = true;
minimeLog[0][nod].first = t;
minimeLog[0][nod].second = c;
h[nod] = adanc;
liniarizare.push_back(nod);
primaAparitie[nod] = liniarizare.size() - 1;
for (int i = 0; i < graf[nod].size(); i++)
{
if (!vizitat[graf[nod][i].first]) /// nu trebuie sa comparam cu tatal, pentru ca e deja vizitat
{
dfs(graf[nod][i].first, nod, graf[nod][i].second, adanc + 1);
liniarizare.push_back(nod);
}
}
}
void precalcPutere2()
{
int putere2 = 1;
int exp = 0;
for (int i = 1; i <= 2 * n - 1; i++)
{
if (putere2 * 2 <= i)
{
putere2 *= 2;
exp++;
}
putere2Max[i] = exp;
}
}
void precalcMinLog()
{
minimeLog[0][0].first = 0;
minimeLog[0][0].second = INT_MAX;
for (int i = 1; i <= putere2Max[n]; i++)
{
minimeLog[i][0].first = 0;
minimeLog[i][0].second = INT_MAX;
for (int j = 1; j <= n; j++)
{
minimeLog[i][j].first = minimeLog[i - 1][minimeLog[i - 1][j].first].first;
minimeLog[i][j].second = min(minimeLog[i - 1][j].second, minimeLog[i - 1][minimeLog[i - 1][j].first].second);
}
}
}
void calcRMQ()
{
for (int i = 1; i <= 2 * n - 1; i++)
{
rmq[i][0].first = liniarizare[i];
rmq[i][0].second = h[liniarizare[i]];
}
for (int l = 1; (1 << l) <= 2 * n - 1; l++)
{
for (int i = 1; i <= 2 * n - 1 - (1 << l) + 1; i++)
{
if (rmq[i][l - 1].second < rmq[i + (1 << (l - 1))][l - 1].second)
{
rmq[i][l].first = rmq[i][l - 1].first;
rmq[i][l].second = rmq[i][l - 1].second;
}
else
{
rmq[i][l].first = rmq[i + (1 << (l - 1))][l - 1].first;
rmq[i][l].second = rmq[i + (1 << (l - 1))][l - 1].second;
}
}
}
}
int minimLant(int nodCrt, int stramos)
{
int distanta = h[nodCrt] - h[stramos];
if (distanta == 0)
return 0;
int minim = INT_MAX;
int indexLog = 0;
while (distanta > 0)
{
if ((1 << indexLog) & distanta)
{
distanta -= (1 << indexLog);
minim = min(minim, minimeLog[indexLog][nodCrt].second);
nodCrt = minimeLog[indexLog][nodCrt].first;
}
indexLog++;
}
return minim;
}
int main()
{
ifstream in("atac.in");
ofstream out("atac.out");
int m, p;
in >> n >> m >> p;
for (int x = 2; x <= n; x++)
{
int y, c;
in >> y >> c;
graf[x].emplace_back(make_pair(y, c));
graf[y].emplace_back(make_pair(x, c));
}
liniarizare.push_back(0);
dfs(1, 0, INT_MAX, 1);
precalcPutere2();
precalcMinLog();
calcRMQ();
int x, y;
in >> x >> y;
int a, b, c, d;
in >> a >> b >> c >> d;
int xCrt = x;
int yCrt = y;
for (int i = 1; i <= m; i++)
{
int xFolosit = xCrt;
int yFolosit = yCrt;
if (primaAparitie[xFolosit] > primaAparitie[yFolosit])
swap(xFolosit, yFolosit);
int stramosComun;
if (rmq[primaAparitie[x]][putere2Max[primaAparitie[y] - primaAparitie[x] + 1]].second < rmq[primaAparitie[y] - (1 << putere2Max[primaAparitie[y] - primaAparitie[x] + 1]) + 1][putere2Max[primaAparitie[y] - primaAparitie[x] + 1]].second)
stramosComun = rmq[primaAparitie[x]][putere2Max[primaAparitie[y] - primaAparitie[x] + 1]].first;
else
stramosComun = rmq[primaAparitie[y] - (1 << putere2Max[primaAparitie[y] - primaAparitie[x] + 1]) + 1][putere2Max[primaAparitie[y] - primaAparitie[x] + 1]].first;
sol.push_back(min(minimLant(xFolosit, stramosComun), minimLant(yFolosit, stramosComun)));
xCrt = (xCrt * a + yCrt * b) % n + 1;
yCrt = (yCrt * c + sol[sol.size() - 1] * d) % n + 1;
}
for (int i = sol.size() - p; i < sol.size(); i++)
out << sol[i] << '\n';
return 0;
}