Pagini recente » Cod sursa (job #1845196) | Cod sursa (job #638386) | Cod sursa (job #1771399) | Cod sursa (job #2760552) | Cod sursa (job #1618119)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <climits>
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
#define MAXN 32000
#define MAXLOG 15
vector < vector < pair <int,int> > > edge;
int father[MAXLOG][MAXN], DP[MAXLOG][MAXN];
int depth[MAXN];
int N, Q, P; int X, Y, A, B, C, D;
void initialize()
{
edge.resize(N+1);
}
void DFS (int node)
{
for (int i = 0; i < edge[node].size(); ++i)
{
if (father[0][node] = edge[node][i].first)
continue;
depth[edge[node][i].first] = depth[node] + 1;
father[0][edge[node][i].first] = node;
DP[0][edge[node][i].first] = edge[node][i].second;
DFS(edge[node][i].first);
}
}
int LCA (int x, int y)
{
if (depth[x] < depth[y])
swap(x,y);
int log1,log2;
for(log1 = 0; (1 << log1) < depth[x]; log1++); //
for(log2 = 0; (1 << log2) < depth[y]; log2++);
for (int i = log1; i >= 0; --i)
if (depth[x] - (1<<i) >= depth[y])
x = father[i][x];
if (x == y)
return 0;
for (int i = log2; i >= 0; --i)
if (father[i][x] != father[i][y] && father[i][x] != 0)
{
x = father[i][x];
y = father[i][y];
}
return father[0][x];
}
int kAncestor (int x, int k)
{
int logarithm;
for (logarithm = 0; (1<<logarithm) < k; ++logarithm);
for (int i = logarithm; i >= 0 && k; --i)
if (k >= (1<<i))
{
k -= (1<<i);
x = father[i][x];
}
return x;
}
int RMQ (int x, int y)
{
if (depth[x] == depth[y])
return INT_MAX;
if (depth[x] < depth[y])
swap(x,y);
int i;
for (i = 0; (1<<i) <= depth[x] - depth[y]; ++i);
--i;
int middle = kAncestor(x, depth[x] - depth[y] - (1<<i));
if (DP[i][x] > DP[i][middle])
return DP[i][middle];
return DP[i][x];
}
int query (int x, int y)
{
if (x == y)
return 0;
int lca = LCA(X,Y);
return min(RMQ(lca,x), RMQ(lca,y));
}
int main()
{
fin >>N >>Q >>P;
initialize();
for (int i = 2; i <= N; ++i)
{
int y, c;
fin >>y >>c;
edge[i].push_back(make_pair(y,c));
edge[y].push_back(make_pair(i, c));
}
fin >>X >>Y >>A >>B >>C >>D;
depth[1] = 1;
DFS(1);
for (int i = 1; (1<<i) <= N; ++i)
for (int j = 1; j <= N; ++j)
father[i][j] = father[i-1][father[i-1][j]];
for(int k = 1; (1 << k) <= N; ++k)
for(int i = 1; i <= N; ++i)
DP[k][i] = min(DP[k-1][i], DP[k-1][father[k-1][i]]);
for(int i = 1; i <= Q; ++i)
{
int Z = query(X,Y);
if(i >= Q - P + 1)
fout <<Z << "\n";
X = (X*A + Y*B)%N + 1;
Y = (Y*C + Z*D)%N + 1;
}
return 0;
}