Cod sursa(job #3136944)

Utilizator rapidu36Victor Manz rapidu36 Data 9 iunie 2023 14:54:50
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.78 kb
#include <fstream>
#include <vector>

using namespace std;

const int N = 32000;
const int L = 14;
const int INF = 1e6;

struct muchie
{
    int vf, c;
};

int n, t[L+1][N+1], b[L+1][N+1], t_i[N+1], t_o[N+1], timp;
vector <muchie> a[N+1];

void dfs(int x)
{
    t_i[x] = ++timp;
    for (auto e: a[x])
    {
        int y = e.vf;
        int c = e.c;
        if (t_i[y] == 0)///y e fiu al lui x in arborele cu rad 1
        {
            t[0][y] = x;
            b[0][y] = c;
            dfs(y);
        }
    }
    t_o[x] = ++timp;
}

void constructie_t_b()
{
    for (int i = 1; (1 << i) <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            t[i][j] = t[i-1][t[i-1][j]];
            if (t[i-1][j] == 0)
            {
                continue;
            }
            b[i][j] = min(b[i-1][j], b[i-1][t[i-1][j]]);
        }
    }
}

bool este_stramos(int x, int y)
{
    return (t_i[x] <= t_i[y] && t_o[y] <= t_o[x]);
}

int lca(int x, int y)
{
    if (este_stramos(x, y))
    {
        return x;
    }
    int pas = L;
    while (pas >= 0)
    {
        if (t[pas][x] != 0 && !este_stramos(t[pas][x] , y))
        {
            x = t[pas][x];
        }
        pas--;
    }
    return t[0][x];
}

///nr. min de bombe necesare pt. a distruge drumul de la x la s (s stramos)
int bombe_drum(int x, int s)
{
    if (s == x)
    {
        return 0;
    }
    int pas = L;
    int nrb = INF;
    while (pas >= 0)
    {
        if (t[pas][x] != 0 && t_i[t[pas][x]] >= t_i[s])
        {
            nrb = min(nrb, b[pas][x]);
            x = t[pas][x];
        }
        pas--;
    }
    return nrb;
}

int interogare(int x, int y)
{
    if (x == y)
    {
        return 0;
    }
    int z = lca(x, y);
    if (z == x)
    {
        return bombe_drum(y, z);
    }
    if (z == y)
    {
        return bombe_drum(x, z);
    }
    return min(bombe_drum(x, z), bombe_drum(y, z));
}

int main()
{
    ifstream in("atac.in");
    ofstream out("atac.out");
    int m, p;
    in >> n >> m >> p;
    for (int i = 2; i <= n; i++)
    {
        int x, c;
        in >> x >> c;
        a[i].push_back((muchie){x, c});
        a[x].push_back((muchie){i, c});
    }
    for (int i = 0; i <= L; i++)
    {
        for (int j = 0; j <= N; j++)
        {
            b[i][j] = INF;
        }
    }
    dfs(1);
    constructie_t_b();
    int x, y, z, a, b, c, d;
    in >> x >> y >> a >> b >> c >> d;
    z = interogare(x, y);
    for (int i = 1; i <= m; i++)
    {
        if (i > m - p)
        {
            out << z << "\n";
        }
        x = (a * x + b * y) % n + 1;
        y = (c * y + z * d) % n + 1;
        z = interogare(x, y);
    }
    in.close();
    out.close();
    return 0;
}