Cod sursa(job #3131244)

Utilizator rapidu36Victor Manz rapidu36 Data 19 mai 2023 16:52:16
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 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 << i); j <= n; j++)
        {
            t[i][j] = t[i-1][t[i-1][j]];
            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 interogare(int x, int y)
{
    int pas = L;
    int nrb = INF;
    while (pas >= 0)
    {
        if (t[pas][x] != 0 && !este_stramos(t[pas][x] , y))
        {
            nrb = min(nrb, b[pas][x]);
            x = t[pas][x];
        }
        pas--;
    }
    nrb = min(nrb, b[0][x]);
    x = t[0][x];
    pas = L;
    while (pas >= 0)
    {
        if (t[pas][y] != 0 && !este_stramos(t[pas][y] , x))
        {
            nrb = min(nrb, b[pas][y]);
            y = t[pas][y];
        }
        pas--;
    }
    nrb = min(nrb, b[0][y]);
    return nrb;
}

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});
    }
    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 = 2; i <= m; i++)
    {
        x = (a * x + b * y) % n + 1;
        y = (c * y + z * d) % n + 1;
        if (i > m - p)
        {
            out << interogare(x, y) << "\n";
        }
    }
    in.close();
    out.close();
    return 0;
}