Pagini recente » Cod sursa (job #1008154) | Cod sursa (job #2935120) | Cod sursa (job #770148) | Cod sursa (job #618677) | Cod sursa (job #2605526)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int INF = 1e9;
const int DIM = 32e3 + 7;
const int LOG = 20;
vector <pair <int, int> > adj[DIM];
int depth[DIM];
int val[DIM];
int dad[DIM][LOG + 1];
int rmq[DIM][LOG + 1];
int lca[DIM * 2][LOG + 1];
int f[DIM];
int timer = 0;
void dfs(int nod, int low = 1, int prev = 0)
{
lca[++timer][0] = nod;
f[nod] = timer;
depth[nod] = low;
dad[nod][0] = prev;
rmq[nod][0] = val[nod];
for(int i = 1; i <= LOG; ++i)
{
dad[nod][i] = dad[dad[nod][i - 1]][i - 1];
rmq[nod][i] = min(rmq[nod][i - 1], rmq[dad[nod][i - 1]][i - 1]);
}
for(auto i : adj[nod])
{
if(i.first == prev)
continue;
val[i.first] = i.second;
dfs(i.first, low + 1, nod);
lca[++timer][0] = nod;
}
}
int get_lca(int x, int y)
{
x = f[x];
y = f[y];
if(x > y)
swap(x, y);
int bit = log2(y - x + 1);
if(depth[lca[x][bit]] < depth[lca[y - (1 << bit) + 1][bit]])
return lca[x][bit];
else
return lca[y - (1 << bit) + 1][bit];
}
int get_ans(int x, int y)
{
if(x == y)
return INF;
int ans = INF;
for(int i = LOG; i >= 0; --i)
{
if(depth[dad[x][i]] >= depth[y])
{
ans = min(ans, rmq[x][i]);
x = dad[x][i];
}
}
return ans;
}
main()
{
int n, q, p;
fin >> n >> q >> p;
for(int i = 2; i <= n; ++i)
{
int x, c;
fin >> x >> c;
adj[x].emplace_back(i, c);
adj[i].emplace_back(x, c);
}
dfs(1);
for(int bit = 1; (1 << bit) <= timer; ++bit)
for(int i = 1; i + (1 << bit) - 1 <= timer; ++i)
if(depth[lca[i][bit - 1]] < depth[lca[i + (1 << (bit - 1))][bit - 1]])
lca[i][bit] = lca[i][bit - 1];
else
lca[i][bit] = lca[i + (1 << (bit - 1))][bit - 1];
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
int prev = 0;
for(int i = 1; i <= q; ++i)
{
int ans = INF;
if(i != 1)
{
x = (x * 1LL * a + y * 1LL * b) % n + 1;
y = (y * 1LL * c + prev * 1LL * d) % n + 1;
}
int god = get_lca(x, y);
ans = min(get_ans(x, god), get_ans(y, god));
if(ans == INF)
{
ans = 0;
}
if(i >= q - p + 1)
fout << ans << '\n';
prev = ans;
}
}