Pagini recente » Cod sursa (job #52477) | Cod sursa (job #280849) | Cod sursa (job #20829) | Cod sursa (job #2304420) | Cod sursa (job #6207)
Cod sursa(job #6207)
#include <stdio.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#define MAX 32007
#define INF 99999999
using namespace std;
int n, m, p;
int nod1, val;
int A, B, C, D, X, Y, Z, N;
int aux_x, aux_y;
vector<vector<int> > lV;
bool caract[MAX];
int noduri[2*MAX];
vector<map<int, int> > ad;
int k, mat[2*MAX][18], nivel[2*MAX];
int part_size;
int first_ap[MAX];
int t[MAX], lca, best;
void convert();
void dfs(int nod, int niv);
int query(int st, int dr);
void rmq();
int main()
{
//read
FILE *fin = fopen("atac.in", "r");
fscanf(fin, "%d%d%d", &n, &m, &p);
lV.resize(n+5);
ad.resize(n+5);
for (int i = 2; i <= n; ++i)
{
fscanf(fin, "%d%d", &nod1, &val);
lV[nod1].push_back(i);
lV[i].push_back(nod1);
ad[nod1][i] = val;
ad[i][nod1] = val;
}
fscanf(fin, "%d%d%d%d%d%d", &X, &Y, &A, &B, &C, &D);
//solve
lV[0].push_back(1);
lV[1].push_back(0);
dfs(0, 0);
rmq();
FILE *fout = fopen("atac.out", "w");
for (int i = 1; i <= m; ++i)
{
lca = noduri[query(first_ap[X], first_ap[Y])];
aux_x = X;
aux_y = Y;
best = INF;
while (t[aux_x] != lca)
{
if (ad[aux_x][t[aux_x]] < best)
best = ad[aux_x][t[aux_x]];
aux_x = t[aux_x];
}
if (ad[aux_x][t[aux_x]] < best)
best = ad[aux_x][t[aux_x]];
while (t[aux_y] != lca)
{
if (ad[aux_y][t[aux_y]] < best)
best = ad[aux_y][t[aux_y]];
aux_y = t[aux_y];
}
if (ad[aux_y][t[aux_y]] < best)
best = ad[aux_y][t[aux_y]];
Z = best;
if ((i-p) >= 0)
fprintf(fout, "%d\n", Z);
// cout << X << " " << Y << " " << Z << "\n";
convert();
}
fclose(fout);
fclose(fin);
return 0;
}
void convert()
{
aux_x = (X * A + Y * B) % n + 1;
aux_y = (Y * C + Z * D) % n + 1;
X = aux_x;
Y = aux_y;
}
void dfs(int nod, int niv)
{
vector<int>::iterator start, end;
start = lV[nod].begin();
end = lV[nod].end();
caract[nod] = true;
noduri[N++] = nod;
nivel[N-1] = niv;
first_ap[nod] = N-1;
for (; start != end; ++start)
if (!caract[(*start)])
{
dfs((*start), niv+1);
t[(*start)] = nod;
noduri[N++] = nod;
nivel[N-1] = niv;
}
}
void rmq()
{
for (int i = 1; i <= N; ++i)
mat[i][0] = i;
for (int j = 1; j <= N; ++j)
{
part_size = (1 << j);
if (part_size > N) break;
for (int i = 1; (i + part_size) - 1 <= N; ++i)
if (nivel[ mat[i][j-1] ] < nivel[ mat[i + part_size / 2 ][j-1] ])
mat[i][j] = mat[i][j-1];
else
mat[i][j] = mat[i + part_size / 2][j-1];
}
}
int query(int st, int dr)
{
if (st > dr) swap(st, dr);
k = (int)floor(log2(dr-st+1));
part_size = (1 << k);
if (nivel[ mat[st][k] ] < nivel[ mat[dr - part_size + 1][k] ])
return mat[st][k];
else
return mat[dr - part_size + 1][k];
}