Cod sursa(job #3361891)

Utilizator serbanbBrindescu Serban serbanb Data 29 iulie 2026 15:21:55
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

const int NMAX = 32000, LOGMAX = 16, VALMAX = 1000000000;

struct node
{
    int depth;
    bool isRoot = true;
    vector<int> children;
};
node tree[NMAX + 5];
int n,m,p,x,y,A,B,C,D;
int up[NMAX + 5][LOGMAX + 5];
int rmq[NMAX + 5][LOGMAX + 5];
int root;

void dfs(int node, int dt)
{
    tree[node].depth = dt;
    for(int i = 0; i < tree[node].children.size(); ++i){
        dfs(tree[node].children[i], dt + 1);
    }
}

int minEdge(int x, int y)
{
    int ans = VALMAX;
    if(x == y){
        return 0;
    }
    if(tree[x].depth < tree[y].depth){
        swap(x, y);
    }
    int levelDiff = tree[x].depth - tree[y].depth;
    for(int i = LOGMAX; i >= 0; --i){
        if(levelDiff & (1 << i)){
            ans = min(ans, rmq[x][i]);
            x = up[x][i];
        }
    }
    if(x == y){
        return ans;
    }
    for(int i = LOGMAX; i >= 0; --i){
        if(up[x][i] != up[y][i]){
            ans = min(ans, rmq[x][i]);
            ans = min(ans, rmq[y][i]);
            x = up[x][i];
            y = up[y][i];
        }
    }
    return min(ans, min(rmq[x][0], rmq[y][0]));
}

int main()
{
    fin >> n >> m >> p;
    for(int i = 2; i <= n; ++i){
        int node, val;
        fin >> node >> val;
        tree[i].isRoot = false;
        up[i][0] = node;
        rmq[i][0] = val;
        tree[node].children.push_back(i);
    }
    for(int j = 1; j <= LOGMAX; ++j){
        for(int i = 1; i <= n; ++i){
            rmq[i][j] = VALMAX;
        }
    }
    for(int j = 1; j <= LOGMAX; ++j){
        for(int i = 1; i <= n; ++i){
            up[i][j] = up[up[i][j - 1]][j - 1];
            rmq[i][j] = min(rmq[i][j - 1], rmq[up[i][j - 1]][j - 1]);
        }
    }
    for(int i = 1; i <= n; ++i){
        if(tree[i].isRoot){
            root = i;
            break;
        }
    }
    dfs(root, 0);
    fin >> x >> y >> A >> B >> C >> D;
    for(int i = 0; i < m; ++i){
        int z = minEdge(x, y);
        if(m - i <= p){
            fout << z << '\n';
        }
        x = (1ll * x * A + 1ll * y * B) % n + 1;
        y = (1ll * y * C + 1ll * z * D) % n + 1;
    }
    return 0;
}