Cod sursa(job #3233520)

Utilizator rapidu36Victor Manz rapidu36 Data 3 iunie 2024 18:59:29
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 = 2e5;

struct muchie
{
    int vf, nrb;
};

vector <muchie> a[N+1];
int s[L+1][N+1], b[L+1][N+1], t_in[N+1], t_out[N+1], timp, n, nivel[N+1];

void dfs(int x)
{
    t_in[x] = ++timp;
    for (auto m: a[x])
    {
        int y = m.vf, nrb = m.nrb;///y este un vecin al lui x
        if (t_in[y] == 0)///y este un fiu al lui x in arborele dfs
        {
            s[0][y] = x;
            b[0][y] = nrb;
            nivel[y] = 1 + nivel[x];
            dfs(y);
        }
    }
    t_out[x] = ++timp;
}

void constructie_s_b()
{
    for (int i = 1; (1 << i) < n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            b[i][j] = INF;
        }
    }
    for (int i = 1; (1 << i) < n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            s[i][j] = s[i-1][s[i-1][j]];
            b[i][j] = min(b[i-1][j], b[i-1][s[i-1][j]]);
        }
    }
}

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

int bombe(int x, int lung)
{
    ///numarul minim de bombe necesare pentru a distruge drumul de lungime lung de la x in sus
    int nrb = INF, i = 0;
    while (lung != 0)
    {
        if (lung % 2 != 0)
        {
            nrb = min(nrb, b[i][x]);
            x = s[i][x];
        }
        i++;
        lung /= 2;
    }
    return nrb;
}

int interogare(int x, int y)
{
    //cout << "LCA (" << x << " , " << y << ") = ";
    if (x == y)
    {
        //cout << 0 << endl;
        return 0;
    }
    int lca = x;
    ///gasim cel mai de sus stramos al lui x care NU e stramos pentru y
    if (!este_stramos(x, y))
    {
        int pas = L;
        while (pas >= 0)
        {
            if (s[pas][lca] != 0 && !este_stramos(s[pas][lca], y))
            {
                lca = s[pas][lca];
            }
            pas--;
        }
        lca = s[0][lca];
    }
    //cout << lca << endl;
    return min(bombe(x, nivel[x] - nivel[lca]), bombe(y, nivel[y] - nivel[lca]));
}

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