Cod sursa(job #3201470)

Utilizator rapidu36Victor Manz rapidu36 Data 8 februarie 2024 15:41:40
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.45 kb
#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;
}