Cod sursa(job #2333186)

Utilizator DavidLDavid Lauran DavidL Data 31 ianuarie 2019 19:17:03
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fi("atac.in");
ofstream fo("atac.out");

const int NMAX = 35000;
const int LOG = 20;

int n, m, pp;
vector < pair<int, int> > G[NMAX];
int h[NMAX], p[NMAX];
int sus[LOG][NMAX];
int minim[LOG][NMAX];
int prima[NMAX];
int lg[NMAX];

void precalcLog()
{
    lg[0] = lg[1] = 0;
    lg[2] = 1;
    for (int i = 3; i < NMAX; i++)
        lg[i] = lg[i / 2] + 1;
}

void dfs(int nod)
{
    for (auto v: G[nod])
        if (v.first != p[nod])
        {
            p[v.first] = nod;
            prima[v.first] = v.second;
            h[v.first] = h[nod] + 1;
            dfs(v.first);
        }
}

void precalcLca()
{
    for (int i = 1; i <= n; i++)
        sus[0][i] = p[i];
    sus[0][1] = -1;

    for (int i = 1; i < LOG; i++)
        for (int j = 1; j <= n; j++)
            sus[i][j] = sus[i - 1][sus[i - 1][j]];
}

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

    if (h[a] < h[b])
        swap(a, b);
    for (int i = lg[h[a] - h[b]]; h[a] != h[b]; i = lg[h[a] - h[b]])
            a = sus[i][a];

    if (a == b)
        return a;

    for (int i = LOG - 1; i >= 0; i--)
        if (h[a] - (1 << i) >= 1 && sus[i][a] != sus[i][b])
            a = sus[i][a], b = sus[i][b];
    return p[a];
}

void precalcMinim() //
{
    for (int i = 2; i <= n; i++)
        minim[0][i] = prima[i];
    minim[0][1] = 1000000;

    for (int i = 1; i < LOG; i++)
        for (int j = 1; j <= n; j++)
            if (h[j] - (1 << i) >= 1)
                minim[i][j] = min(minim[i - 1][j], minim[i - 1][sus[i - 1][j]]);
            else
                minim[i][j] = 1000000;
}

int getminim(int a, int b) // minimul pe drumul dintre a si b (b este stramos al lui a)
{
    if (a == b)
        return 1000000;

    if (h[a] < h[b])
        swap(a, b);

    int ret = 1000000;
    for (int i = lg[h[a] - h[b]]; a != b; i = lg[h[a] - h[b]])
    {
        ret = min(ret, minim[i][a]);
        a = sus[i][a];
    }
    return ret;
}

int main()
{
    fi >> n >> m >> pp;
    for (int i = 2;  i <= n; i++)
    {
        int v, c;
        fi >> v >> c;
        G[i].push_back({v, c});
        G[v].push_back({i, c});
    }

    precalcLog();
    h[1] = 1; dfs(1);
    precalcLca();
    precalcMinim();

    //cout << sus[0][4];
    //return 0;
    int x, y, a, b, c, d;
    fi >> x >> y >> a >> b >> c >> d;
    for (int i = 1; i <= m; i++)
    {
        int cost;
        if (x == y)
            cost = 0;
        else
        {
            int comun = lca(x, y);
            cost = min(getminim(x, comun), getminim(y, comun));
        }
        //fo << "(" << x << ", " << y << ")\n";
        if (i >= m - pp + 1)
            fo << cost << "\n";

        int cx = x, cy = y;
        x = (cx * a + cy * b) % n + 1;
        y = (cy * c + cost * d) % n + 1;
    }

    return 0;
}