Cod sursa(job #30423)

Utilizator victorsbVictor Rusu victorsb Data 13 martie 2007 22:33:31
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <cstdio>
#include <vector>

using namespace std;

#define Nmax 32768
#define Kmax 16
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define sz size()
#define nd first
#define cost second

int n, m, p, x, y, a, b, c, d, ct;
vector<pair<int, int> > lv[Nmax];
int str[Kmax][Nmax], mat[Kmax][Nmax], ad[Nmax], drum[4 * Nmax], v[Nmax], poz[Nmax], rmq[Kmax][4 * Nmax];

void citire()
{
    int i;
    
    scanf("%d %d %d\n", &n, &m, &p);
    for (i = 2; i <= n; ++i)
    {
        scanf("%d %d\n", &a, &c);
        lv[i].pb(mp(a, c));
        lv[a].pb(mp(i, c));
    }
    scanf("%d %d %d %d %d %d\n", &x, &y, &a, &b, &c, &d);
}

void df(int nod)
{
    int i, lim = lv[nod].sz;
    
    v[nod] = 1;
    drum[++ct] = nod;
    poz[nod] = ct;
    
    for (i = 0; i < lim; ++i)
        if (!v[lv[nod][i].nd])
        {
            ad[lv[nod][i].nd] = ad[nod] + 1;
            mat[0][lv[nod][i].nd] = lv[nod][i].cost;
            str[0][lv[nod][i].nd] = nod;
            
            df(lv[nod][i].nd);
            drum[++ct] = nod;
        }
}

int lca(int x, int y)
{
    int k;
    if (x > y)
        swap(x, y);
    
    for (k = Kmax - 1; k >= 0; --k)
        if (x + (1 << k) - 1 <= y)
            break;
    
    if (ad[ rmq[k][x] ] < ad[ rmq[k][y - (1 << k) + 1] ])
        return rmq[k][x];
    else
        return rmq[k][y - (1 << k) + 1];
}

int query(int x, int y)
{
    int k, h, ret = INF;
    
    h = ad[ lca(poz[x], poz[y]) ];
    
    for (k = Kmax - 1; k >= 0; --k)
        if (ad[x] - h >= (1 << k))
        {
            if (ret > mat[k][x])
                ret = mat[k][x];
            x = str[k][x];
        }
    
    for (k = Kmax - 1; k >= 0; --k)
        if (ad[y] - h >= (1 << k))
        {
            if (ret > mat[k][y])
                ret = mat[k][y];
            y = str[k][y];
        }
    
    return ret;
}

void solve()
{
    int i, j, z, x1, y1;
    
    ad[1] = 1;
    df(1);
    
    for (i = 1; i <= ct; ++i)
        rmq[0][i] = drum[i];
    
    for (i = 1; i < Kmax; ++i)
        for (j = 1; j + (1 << i) - 1 <= ct; ++j)
            if (ad[ rmq[i - 1][j] ] < ad[ rmq[i - 1][j + (1 << (i - 1))] ])
                rmq[i][j] = rmq[i - 1][j];
            else
                rmq[i][j] = rmq[i - 1][j + (1 << (i - 1))];
    
    for (i = 1; i < Kmax; ++i)
        for (j = 1; j <= n; ++j)
            if (ad[j] - (1 << i) > 0)
                str[i][j] = str[i - 1][str[i - 1][j]];
    
    for (i = 1; i < Kmax; ++i)
        for (j = 1; j <= n; ++j)
            if (ad[j] - (1 << i) > 0)
                mat[i][j] = min( mat[i - 1][j], mat[i - 1][str[i - 1][j]]);
    
    for (i = m; i >= 1; --i, x = x1, y = y1)
    {
        x1 = (x * a + y * b) % n + 1;
        y1 = (y * c + z * d) % n + 1;
        z = query(x, y);
        if (i <= p)
            printf("%d\n", z);
    }
}

int main()
{
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
    citire();
    solve();
    return 0;
}