Pagini recente » Cod sursa (job #37658) | Cod sursa (job #3207213) | Cod sursa (job #68289) | Cod sursa (job #205172) | Cod sursa (job #3233521)
#include <fstream>
#include <vector>
using namespace std;
const int N = 32000;
const int L = 14;
const int INF = 2e5;
struct muchie
{
int vf, nrb;
};
vector <muchie> a[N+1];
int s[L+1][N+1], b[L+1][N+1], t_in[N+1], t_out[N+1], timp, n, nivel[N+1];
void dfs(int x)
{
t_in[x] = ++timp;
for (auto m: a[x])
{
int y = m.vf, nrb = m.nrb;///y este un vecin al lui x
if (t_in[y] == 0)///y este un fiu al lui x in arborele dfs
{
s[0][y] = x;
b[0][y] = nrb;
nivel[y] = 1 + nivel[x];
dfs(y);
}
}
t_out[x] = ++timp;
}
void constructie_s_b()
{
for (int i = 1; (1 << i) < n; i++)
{
for (int j = 1; j <= n; j++)
{
b[i][j] = INF;
}
}
for (int i = 1; (1 << i) < n; i++)
{
for (int j = 1; j <= n; j++)
{
s[i][j] = s[i-1][s[i-1][j]];
b[i][j] = min(b[i-1][j], b[i-1][s[i-1][j]]);
}
}
}
bool este_stramos(int x, int y)
{
return (t_in[x] <= t_in[y] && t_out[y] <= t_out[x]);
}
int bombe(int x, int lung)
{
///numarul minim de bombe necesare pentru a distruge drumul de lungime lung de la x in sus
int nrb = INF, i = 0;
while (lung != 0)
{
if (lung % 2 != 0)
{
nrb = min(nrb, b[i][x]);
x = s[i][x];
}
i++;
lung /= 2;
}
return nrb;
}
int interogare(int x, int y)
{
if (x == y)
{
return 0;
}
int lca = x;
///gasim cel mai de sus stramos al lui x care NU e stramos pentru y
if (!este_stramos(x, y))
{
int pas = L;
while (pas >= 0)
{
if (s[pas][lca] != 0 && !este_stramos(s[pas][lca], y))
{
lca = s[pas][lca];
}
pas--;
}
lca = s[0][lca];
}
return min(bombe(x, nivel[x] - nivel[lca]), bombe(y, nivel[y] - nivel[lca]));
}
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 = i, y, nrb;
in >> y >> nrb;
a[x].push_back((muchie){y, nrb});
a[y].push_back((muchie){x, nrb});
}
dfs(1);
constructie_s_b();
int x, y, a, b, c, d;
in >> x >> y >> a >> b >> c >> d;
for (int i = 0; i < m; i++)
{
int z = interogare(x, y);
if (i >= m - p)
{
out << z << "\n";
}
x = (x*a + y*b) % n + 1;
y = (y*c + z*d) % n + 1;
}
in.close();
out.close();
return 0;
}