Cod sursa(job #3171787)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 19 noiembrie 2023 16:07:18
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <bits/stdc++.h>

using namespace std;

#define MAX_N 32000

struct Node
{
    int ancestor, minCost;
};

int n, m, p, L, timer;
vector <int> tin, tout, height;
vector <vector <pair <int, int> > > graph;
vector <vector <Node> > dp;
bitset <MAX_N + 1> viz;

void dfs(int node, int parent, int edgeCost, int h)
{
    viz[node] = 1;
    tin[node] = ++timer;
    height[node] = h;

    dp[0][node].minCost = edgeCost;
    dp[0][node].ancestor = parent;
    for(int i = 1; i <= L; i ++)
    {
        dp[i][node].ancestor = dp[i - 1][dp[i - 1][node].ancestor].ancestor;
        dp[i][node].minCost = min(dp[i - 1][node].minCost, dp[i - 1][dp[i - 1][node].ancestor].minCost);
    }

    for(pair <int, int> neighbour : graph[node])
        if(!viz[neighbour.first])
            dfs(neighbour.first, node, neighbour.second, h + 1);
    tout[node] = ++timer;
}

bool isAncestor(int a, int b)
{
    return (tin[a] <= tin[b]  &&  tout[b] <= tout[a]);
}

int lca(int a, int b)
{
    if(isAncestor(a, b))
        return  a;
    if(isAncestor(b, a))
        return b;

    for(int i = L; i >= 0; i --)
    {
        if(!isAncestor(dp[i][a].ancestor,b))
            a = dp[i][a].ancestor;
    }
    return dp[0][a].ancestor;
}

int solve(int firstNode, int secondNode)
{
//    if(firstNode < 1  || secondNode < 1)
//        exit(0);
    if(firstNode == secondNode)
        return 0;
    int centru = lca(firstNode, secondNode);
//    cout << centru << "\n";

    int ans = INT_MAX;

//    cout << firstNode << " " << secondNode << "\n";
    for(int i = L; i >= 0; i --)
    {
//        cout << "ancestor " <<dp[i][firstNode].ancestor << "\n";
        if(height[dp[i][firstNode].ancestor] >= height[centru])
        {
//            cout << dp[i][firstNode].ancestor << " " << height[dp[i][firstNode].ancestor] << " " << height[centru] << " " << dp[i][firstNode].minCost << "\n";
            ans = min(ans, dp[i][firstNode].minCost);
            firstNode = dp[i][firstNode].ancestor;
        }
        if(height[dp[i][secondNode].ancestor] >= height[centru])
        {
            ans = min(ans, dp[i][secondNode].minCost);
            secondNode = dp[i][secondNode].ancestor;
        }
    }
    return ans;
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);

    cin >> n >> m >> p;
    graph.resize(n + 1);

    for(int i = 2; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[i].push_back({a, b});
        graph[a].push_back({i, b});
    }

//    for(int i = 1; i <= n; i ++)
//    {
//        cout << i << "\n";
//        for(auto neighbour : graph[i])
//            cout << i << " " << neighbour.first << " " << neighbour.second << "\n";
//        cout << "\n";
//    }

    int x, y, a, b, c, d, z;
    cin >> x >> y >> a >> b >> c >> d;

    L = log2(n);
    tin.resize(n + 1);
    tout.resize(n + 1);
    height.resize(n + 1);
    dp.resize(L + 1, vector <Node> (n + 1));
    dfs(1, 1, INT_MAX, 1);

    for(int i = 1; i <= m - p; i ++)
    {
        z = solve(x, y);
//        cout << z << "\n";
//        cout << "end solve \n";
        int copyX = x, copyY = y;
        x = (copyX * a + copyY * b) % n + 1; //intra in int
        y = (copyY * c + z * d) % n + 1;
    }

    for(int i = m - p + 1; i <= m; i ++)
    {
//        cout << x << " " << y << "\n";
        z = solve(x, y);
        cout << z << "\n";
//        cout << "end solve \n";
        int copyX = x, copyY = y;
        x = (copyX * a + copyY * b) % n + 1; //intra in int
        y = (copyY * c + z * d) % n + 1;
//        cout << "\n";
    }
    return 0;
}