Pagini recente » Cod sursa (job #2011114) | Cod sursa (job #1892995) | Cod sursa (job #3348288) | Cod sursa (job #834030) | Cod sursa (job #3304271)
#include <bits/stdc++.h>
using namespace std;
#define ST_DIO 0
#if ST_DIO
#define fin cin
#define fout cout
#else
ifstream fin("atac.in");
ofstream fout("atac.out");
#endif // ST_DIO
const int LOG_MAX = 15;
struct Muchie {
int vec, cost;
};
int n, m, p, i, x, y, z, a, b, c, d;
vector<Muchie> gr[32002];
int rmq[LOG_MAX + 2][32002];
int tata[LOG_MAX + 2][32002];
int niv[32002];
static inline void DFS(int nod = 1, int tataNod = 0, int cost = 0, int nivNod = 1) {
tata[0][nod] = tataNod;
rmq[0][nod] = cost;
niv[nod] = nivNod;
for(Muchie urm : gr[nod]) {
if(urm.vec != tataNod) DFS(urm.vec, nod, urm.cost, 1 + nivNod);
}
}
static inline int LCA(int x, int y) {
if(x == y) return 0;
if(niv[x] < niv[y]) swap(x, y);
int costMi = INT_MAX;
int dif = niv[x] - niv[y];
for(int put = LOG_MAX - 1; put >= 0; put--) {
if(dif >> put & 1) {
costMi = min(costMi, rmq[put][x]);
x = tata[put][x];
}
}
if(x == y) return costMi;
for(int put = LOG_MAX - 1; put >= 0; put--) {
if(tata[put][x] != tata[put][y]) {
costMi = min({costMi, rmq[put][x], rmq[put][y]});
x = tata[put][x];
y = tata[put][y];
}
}
costMi = min({costMi, rmq[0][x], rmq[0][y]});
return costMi;
}
int main() {
if(ST_DIO) ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n >> m >> p;
for(i = 2; i <= n; i++) {
int x, c;
fin >> x >> c;
gr[i].push_back({x, c});
gr[x].push_back({i, c});
}
DFS();
for(int put = 1; put < LOG_MAX; put++) {
for(i = 1; i <= n; i++) tata[put][i] = tata[put - 1][tata[put - 1][i]];
for(i = 1; i <= n; i++) rmq[put][i] = min(rmq[put - 1][i], rmq[put - 1][tata[put - 1][i]]);
}
fin >> x >> y >> a >> b >> c >> d;
for(i = 1; i <= m; i++) {
z = LCA(x, y);
if(m - p + 1 <= i) fout << z << "\n";
x = 1LL * (x * a + b * y) % n + 1;
y = 1LL * (y * c + z * d) % n + 1;
}
return 0;
}