Pagini recente » Cod sursa (job #1925498) | Cod sursa (job #1483053) | Cod sursa (job #111206) | Cod sursa (job #253899) | Cod sursa (job #3201470)
#include <fstream>
#include <vector>
using namespace std;
const int N = 32000;
const int L = 14;
const int INF = 1000000;
ifstream fin("atac.in");
ofstream fout("atac.out");
int queries, remainingQueries;
struct Edge
{
int destination, cost;
};
int nodes, timeTable[L + 1][N + 1], bombs[L + 1][N + 1], inTime[N + 1], outTime[N + 1], currentTime;
vector<Edge> adjacencyList[N + 1];
void BuildTimeBombsTables()
{
for (int i = 1; (1 << i) <= nodes; i++)
{
for (int j = 1; j <= nodes; j++)
{
timeTable[i][j] = timeTable[i - 1][timeTable[i - 1][j]];
if (timeTable[i - 1][j] == 0)
{
continue;
}
bombs[i][j] = min(bombs[i - 1][j], bombs[i - 1][timeTable[i - 1][j]]);
}
}
}
void DepthFirstSearch(int current)
{
inTime[current] = ++currentTime;
for (auto edge : adjacencyList[current])
{
int neighbor = edge.destination;
int cost = edge.cost;
if (inTime[neighbor] == 0)
{
timeTable[0][neighbor] = current;
bombs[0][neighbor] = cost;
DepthFirstSearch(neighbor);
}
}
outTime[current] = ++currentTime;
}
bool IsAncestor(int ancestor, int descendant)
{
return (inTime[ancestor] <= inTime[descendant] && outTime[descendant] <= outTime[ancestor]);
}
int LowestCommonAncestor(int x, int y)
{
if (IsAncestor(x, y))
{
return x;
}
int step = L;
while (step >= 0)
{
if (timeTable[step][x] != 0 && !IsAncestor(timeTable[step][x], y))
{
x = timeTable[step][x];
}
step--;
}
return timeTable[0][x];
}
int BombsRequiredForPath(int start, int ancestor)
{
if (ancestor == start)
{
return 0;
}
int step = L;
int requiredBombs = INF;
while (step >= 0)
{
if (timeTable[step][start] != 0 && inTime[timeTable[step][start]] >= inTime[ancestor])
{
requiredBombs = min(requiredBombs, bombs[step][start]);
start = timeTable[step][start];
}
step--;
}
return requiredBombs;
}
int Query(int x, int y)
{
if (x == y)
{
return 0;
}
int commonAncestor = LowestCommonAncestor(x, y);
if (commonAncestor == x)
{
return BombsRequiredForPath(y, commonAncestor);
}
if (commonAncestor == y)
{
return BombsRequiredForPath(x, commonAncestor);
}
return min(BombsRequiredForPath(x, commonAncestor), BombsRequiredForPath(y, commonAncestor));
}
int main()
{
fin >> nodes >> queries >> remainingQueries;
for (int i = 2; i <= nodes; i++)
{
int parent, cost;
fin >> parent >> cost;
adjacencyList[i].push_back(Edge{parent, cost});
adjacencyList[parent].push_back(Edge{i, cost});
}
for (int i = 0; i <= L; i++)
for (int j = 0; j <= N; j++)
bombs[i][j] = INF;
DepthFirstSearch(1);
BuildTimeBombsTables();
int x, y, a, b, c, d, result;
fin >> x >> y >> a >> b >> c >> d;
result = Query(x, y);
for (int i = 1; i <= queries; i++)
{
if (i > queries - remainingQueries)
{
fout << result << "\n";
}
x = (a * x + b * y) % nodes + 1;
y = (c * y + result * d) % nodes + 1;
result = Query(x, y);
}
return 0;
}