Pagini recente » Sliding Window | Monitorul de evaluare | Wbtree | Monitorul de evaluare | Cod sursa (job #3133670)
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("atac.in");
ofstream out ("atac.out");
struct str{
int x, c;
};
struct mch{
int x, y, c;
};
const int max_size = 15e3 + 1, rmax = 15, INF = 1e9 + 1;
int lvl[max_size], lg[max_size], f[max_size];
str t[rmax][max_size];
vector <str> mc[max_size];
vector <mch> apm;
void dfs (int nod, int par, int cost)
{
// out << par << " " << nod << '\n';
t[0][nod].x = par;
t[0][nod].c = cost;
lvl[nod] = lvl[par] + 1;
for (auto f : mc[nod])
{
if (f.x != par)
{
dfs(f.x, nod, f.c);
}
}
}
str anc (int x, int ord)
{
str ans = {x, INF};
int e = 0;
while (ord > 0)
{
if (ord % 2 == 1)
{
ans.x = t[e][x].x;
ans.c = min(t[e][x].c, ans.c);
x = t[e][x].x;
}
e++;
ord /= 2;
}
return ans;
}
int lca (int x, str ry)
{
int mx1 = INF, mx2 = ry.c, y = ry.x;
int e = lg[lvl[x]];
while (e >= 0)
{
if (t[e][x].x != t[e][y].x)
{
mx1 = min(t[e][x].c, mx1);
x = t[e][x].x;
mx2 = min(t[e][y].c, mx2);
y = t[e][y].x;
}
e--;
}
return min(min(mx1, mx2), min(t[0][x].c, t[0][y].c));
}
int main ()
{
int n, m, q;
in >> n >> m >> q;
for (int i = 2; i <= n; i++)
{
int x, c;
in >> x >> c;
mc[x].push_back({i, c});
mc[i].push_back({x, c});
}
dfs(1, 0, 0);
for (int e = 1; e < rmax; e++)
{
for (int i = 1; i <= n; i++)
{
t[e][i].x = t[e - 1][t[e - 1][i].x].x;
t[e][i].c = min(t[e - 1][i].c, t[e - 1][t[e - 1][i].x].c);
}
}
for (int i = 2; i <= n; i++)
{
lg[i] = lg[i /2] + 1;
}
int x, y, a, b, c, d;
in >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= m; i++)
{
int ans;
if (lvl[x] > lvl[y])
{
swap(x, y);
}
str ry = anc(y, lvl[y] - lvl[x]);
if (ry.x == x)
{
ans = ry.c;
}
else
{
ans = lca(x, ry);
}
if (i > m - q)
{
out << ans << '\n';
}
int xp = (x * a + y * b) % n + 1, yp = (y * c + ans * d) % n + 1;
x = xp;
y = yp;
}
in.close();
out.close();
return 0;
}