Cod sursa(job #2697913)

Utilizator dimi999Dimitriu Andrei dimi999 Data 20 ianuarie 2021 13:33:54
Problema Atac Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.52 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 Aint
{
    int V[150000];

    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            V[node] = val[st];
            return;
        }

        int mij = (st + dr) / 2;

        build(2 * node, st, mij);
        build(2 * node + 1, mij + 1, dr);

        V[node] = min(V[2 * node], V[2 * node + 1]);
    }

    int query(int node, int st, int dr, int l, int r)
    {
        if(st >= l && dr <= r)
            return V[node];

        if(st > r || dr < l)
            return INT_MAX;

        int mij = (st + dr) / 2;

        return min(query(2 * node, st, mij, l, r),
                   query(2 * node + 1, mij + 1, dr, l, r));
    }
}aint;

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 aint.query(1, 1, N, a + 1, b);
    }

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

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

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

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

        return min(aint.query(1, 1, N, 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);

    aint.build(1, 1, N);

    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;
}