Cod sursa(job #2697924)

Utilizator dimi999Dimitriu Andrei dimi999 Data 20 ianuarie 2021 14:25:01
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <fstream>
#include <vector>
#include <climits>

using namespace std;

struct Edges
{
    int dest, cost;
};

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

vector <Edges> v[32005];

int sz[32005], label[32005], k, level[32005], N;
int head[32005], dads[32005];

void get_size(int node, int dad)
{
    sz[node]++;
    dads[node] = dad;
    level[node] = level[dad] + 1;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dad)
    {
        get_size(v[node][i].dest, node);
        sz[node] += sz[v[node][i].dest];
    }
}

void dfsGreu(int node, int dad)
{
    label[node] = ++k;

    int maxi, heavySon = v[node][0].dest;

    if(heavySon == dad && v[node].size() > 1)
        heavySon = v[node][1].dest;

    maxi = sz[heavySon];

    if(v[node].size() == 1 && dad != 0)
        return;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dad && sz[v[node][i].dest] > maxi)
            maxi = sz[v[node][i].dest], heavySon = v[node][i].dest;

    head[heavySon] = head[node];
    dfsGreu(heavySon, node);

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dad && v[node][i].dest != heavySon)
        dfsGreu(v[node][i].dest, node);

}

int val[32005];

struct RMQ
{
    int V[20][35000];

    int puteri[35000];

    void build()
    {
        for(int i = 2; i <= N; i++)
            puteri[i] = puteri[i / 2] + 1;

        for(int i = 1; i <= N; i++)
            V[0][i] = val[i];

        for(int i = 1; (1 << i) <= N; i++)
            for(int j = 1; j <= N - (1 << i) + 1; j++)
                V[i][j] = min(V[i - 1][j], V[i - 1][j + (1 << (i - 1))]);
    }

    int query(int a, int b)
    {
        int dif = b - a + 1;

        int line = puteri[dif], column = dif - (1 << line);

        return min(V[line][a], V[line][a + column]);
    }
}rmq;

void get_val(int node, int cost)
{
    val[label[node]] = cost;

    for(int i = 0; i < v[node].size(); i++)
        if(v[node][i].dest != dads[node])
            get_val(v[node][i].dest, v[node][i].cost);
}

int sol(int x, int y)
{
    if(head[x] == head[y])
    {
        int a, b;

        a = label[x];
        b = label[y];

        if(a > b)
            swap(a, b);

        return rmq.query(a + 1, b);
    }

    if(level[head[x]] > level[head[y]])
    {
        int a, b;

        a = label[head[x]];
        b = label[x];

        return min(rmq.query(a, b), sol(dads[head[x]], y));
    }
    else
    {
        int a, b;

        a = label[head[y]];
        b = label[y];

        return min(rmq.query(a, b), sol(x, dads[head[y]]));
    }

}



int main()
{
    int M, P;

    fin >> N >> M >> P;

    for(int i = 2; i <= N; i++)
    {
        int x, y;

        fin >> x >> y;

        v[x].push_back({i, y});
        v[i].push_back({x, y});
    }

    get_size(1, 0);

    for(int i = 1; i <= N; i++)
        head[i] = i;

    dfsGreu(1, 0);

    get_val(1, 0);

    rmq.build();

    int A, B, C, D, X, Y;

    fin >> X >> Y >> A >> B >> C >> D;

    while(M != 0)
    {
        int ans;

        if(X == Y)
            ans = 0;
        else
            ans = sol(X, Y);

        if(M <= P)
            fout << ans << '\n';

        X = (X * A + Y * B) % N + 1;
        Y = (Y * C + ans * D) % N + 1;
        M--;
    }

    return 0;
}