Cod sursa(job #1519873)

Utilizator akaprosAna Kapros akapros Data 7 noiembrie 2015 22:59:54
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxN 32002
#define inf 2000000000
#define maxL 18
using namespace std;
int n, m, p, q, nr, ne;
int anc[maxN][maxL], dp[maxN][maxL];
int r[maxN * 2][maxL], e[maxN * 2], lev[maxN * 2], urm[2 * maxN], vf[maxN * 2], Vf[maxN * 2], lst[maxN], t[maxN], pos[maxN], d[maxL][maxN * 2], Log[maxN * 2];
void add(int x, int y, int z)
{
    ++ nr;
    vf[nr] = y;
    Vf[nr] = z;
    urm[nr] = lst[x];
    lst[x] = nr;
}
void read()
{
    int i, j, x, z;
    freopen("atac.in", "r", stdin);
    scanf("%d %d %d", &n, &m, &q);
    lev[0] = -1;
    for (i = 2; i <= n; ++ i)
    {
        scanf("%d %d", &x, &z);
        anc[i][0] = x;
        add(x, i, z);
    }
}
void euler(int x)
{
    e[++ ne] = x;
    if (pos[x] == 0)
        pos[x] = ne;
    lev[x] = lev[anc[x][0]] + 1;
    int p = lst[x], y;
    while (p != 0)
    {
        y = vf[p];
        euler(y);
        e[++ ne] = x;
        p = urm[p];
    }
}
void dfs(int x, int z)
{
    int i;
    int p = lst[x], y;
    dp[x][0] = z;
        for (nr = 1; (1 << nr) <= lev[x]; nr++)
        {
            dp[x][nr] = min(dp[x][nr-1] , dp[anc[x][nr-1]][nr-1]);
            anc[x][nr] = anc[anc[x][nr-1]][nr-1];
        }
    while (p)
    {
        dfs(vf[p], Vf[p]);
        p = urm[p];
    }
}
void solve()
{
    int i, j;
    for (i = 1; i <= ne; ++ i)
        d[0][i] = e[i];
    for (i = 2; i <= ne; ++ i)
        Log[i] = Log[i / 2] + 1;
    for (i = 1; i <= Log[ne]; ++ i)
        for (j = 1; j <= ne; ++ j)
        {
            d[i][j] = d[i - 1][j - (1 << (i - 1))];
            if (lev[d[i][j]] > lev[d[i - 1][j]])
                d[i][j] = d[i - 1][j];
        }
}
int minw(int x, int y)
{
    if (x == y)
        return inf;
    int k = Log[lev[x]-lev[y]];
    return (min(dp[x][k] , minw(anc[x][k] , y)));
}
void write()
{
    int z, t, x, y, k, A, B, C, D;
    freopen("atac.out", "w", stdout);
    scanf("%d %d %d %d %d %d", &x, &y, &A, &B, &C, &D);
    while (m --)
    {
        z = pos[x];
        t = pos[y];
        if (z > t)
            swap(z, t);
        k = Log[t - z];
        if (lev[d[k][t]] < lev[d[k][z + (1 << k)-1]])
            p = d[k][t];
        else
            p = d[k][z + (1 << k)-1];
        if (x == y)
            z = 0;
        else
        z = min(minw(x, p), minw(y, p));
        if (m < q)
            printf("%d\n", z);
        x = (x * A + y * B) % n + 1;
        y = (y * C + z * D) % n + 1;
    }
}
int main()
{
    read();
    euler(1);
    dfs(1, 0);
    solve();
    write();
    return 0;
}