Pagini recente » Cod sursa (job #2916745) | Cod sursa (job #1760499) | Cod sursa (job #1993566) | Cod sursa (job #2029302) | Cod sursa (job #3133684)
#include <fstream>
#include <vector>
using namespace std;
const int N = 32000;
const int L = 14;
const int INF = 1e6;
struct muchie
{
int vf, c;
};
int n, t[L+1][N+1], b[L+1][N+1], t_i[N+1], t_o[N+1], timp;
vector <muchie> a[N+1];
void dfs(int x)
{
t_i[x] = ++timp;
for (auto e: a[x])
{
int y = e.vf;
int c = e.c;
if (t_i[y] == 0)///y e fiu al lui x in arborele cu rad 1
{
t[0][y] = x;
b[0][y] = c;
dfs(y);
}
}
t_o[x] = ++timp;
}
void constructie_t_b()
{
for (int i = 1; (1 << i) <= n; i++)
{
for (int j = 1; j <= n; j++)
{
t[i][j] = t[i-1][t[i-1][j]];
if (t[i-1][j] == 0)
{
continue;
}
b[i][j] = min(b[i-1][j], b[i-1][t[i-1][j]]);
}
}
}
bool este_stramos(int x, int y)
{
return (t_i[x] <= t_i[y] && t_o[y] <= t_o[x]);
}
int lca(int x, int y)
{
if (este_stramos(x, y))
{
return x;
}
int pas = L;
while (pas >= 0)
{
if (t[pas][x] != 0 && !este_stramos(t[pas][x] , y))
{
x = t[pas][x];
}
pas--;
}
return t[0][x];
}
///nr. min de bombe necesare pt. a distruge drumul de la x la s (s stramos)
int bombe_drum(int x, int s)
{
if (s == x)
{
return 0;
}
int pas = L;
int nrb = INF;
while (pas >= 0)
{
if (t[pas][x] != 0 && t_i[t[pas][x]] >= t_i[s])
{
nrb = min(nrb, b[pas][x]);
x = t[pas][x];
}
pas--;
}
return nrb;
}
int interogare(int x, int y)
{
if (x == y)
{
return 0;
}
int z = lca(x, y);
if (z == x)
{
return bombe_drum(y, z);
}
if (z == y)
{
return bombe_drum(x, z);
}
return min(bombe_drum(x, z), bombe_drum(y, z));
}
int main()
{
ifstream in("atac.in");
ofstream out("atac.out");
int m, p;
in >> n >> m >> p;
for (int i = 2; i <= n; i++)
{
int x, c;
in >> x >> c;
a[i].push_back((muchie){x, c});
a[x].push_back((muchie){i, c});
}
for (int i = 0; i <= L; i++)
{
for (int j = 0; j <= N; j++)
{
b[i][j] = INF;
}
}
dfs(1);
constructie_t_b();
int x, y, z, a, b, c, d;
in >> x >> y >> a >> b >> c >> d;
z = interogare(x, y);
for (int i = 2; i <= m; i++)
{
x = (a * x + b * y) % n + 1;
y = (c * y + z * d) % n + 1;
if (i > m - p)
{
out << interogare(x, y) << "\n";
}
}
in.close();
out.close();
return 0;
}