Cod sursa(job #986250)

Utilizator FlameingoAiordachioaei Marius Flameingo Data 18 august 2013 12:47:29
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#define n first
#define c second
using namespace std;

const int NMAX = 32003, INFI = 2e9;

vector <int> A[NMAX];
pair <int, int> D[16][NMAX];
int Ep[NMAX], s, N, niv[NMAX], l2[2 * NMAX], R[17][2 * NMAX];

void DFS (const int &nod) {

    R[0][++s] = nod;
    Ep[nod] = s;
    l2[s + 1] = l2[s + 1 >> 1] + 1;
    for (vector <int> :: iterator i = A[nod].begin (); i != A[nod].end (); ++i) {
        niv[*i] = niv[nod] + 1;
        DFS (*i);
        R[0][++s] = nod;
        Ep[nod] = s;
        l2[s + 1] = l2[s + 1 >> 1] + 1;
    }

}

inline int _min (const int &a, const int &b) {

    return niv[a] < niv[b] ? a : b;

}

inline void RMQ_build () {

    int i, j, l, d;
    for (i = 1; (1 << i) <= s; ++i)
        for (l = s - (1 << i) + 1, d = 1 << i - 1, j = 1; j <= l; ++j)
            R[i][j] = _min (R[i - 1][j], R[i - 1][j + d]);

}

inline int LCA_query (int nod, int _nod) {

    nod = Ep[nod];
    _nod = Ep[_nod];
    if (nod > _nod)
        swap (nod, _nod);
    int l = _nod - nod + 1;
    return _min (R[l2[l]][nod], R[l2[l]][nod + l - (1 << l2[l])]);

}

inline void DIN_build () {

    int i, j;
    for (i = 2; (1 << i) <= N; ++i)
        for (j = 1; j <= N; ++j)
            D[i][j].n = D[i - 1][D[i - 1][j].n].n,
            D[i][j].c = min (D[i - 1][j].c, D[i - 1][D[i - 1][j].n].c);

}

inline int DIN_query (const int &nod, int _nod) {

    int l = niv[_nod] - niv [nod] + 1, mx = INFI;
    while (l != 1) {
        mx = min (mx, D[l2[l]][_nod].c);
        _nod = D[l2[l]][_nod].n;
        l -= l2[l];
    }
    return mx;

}

inline int query (const int &nod,const int &_nod) {

    if (nod == _nod)
        return 0;
    int lca = LCA_query (nod, _nod);
    return min (DIN_query (lca, nod), DIN_query (lca, _nod));

}

int main () {

    freopen ("atac.in", "r", stdin);
    freopen ("atac.out", "w", stdout);
    int M, P, i, a, b, c, d, k, x, y, z, _x, _y;
    D[1][1].c = INFI;
    scanf ("%d%d%d", &N, &M, &P);
    for (i = 2; i <= N; ++i)
        scanf ("%d%d", &a, &b),
        D[1][i] = make_pair (a, b),
        A[a].push_back (i);
    DFS (1);
    RMQ_build ();
    DIN_build ();
    k = M - P;
    scanf ("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
    for (i = 1; i <= k; ++i)
        z = query (x, y),
        _x = (x * a + y * b) % N + 1,
        _y = (y * c + z * d) % N + 1,
        x = _x,
        y = _y;
    while (P--)
        z = query (x, y),
        _x = (x * a + y * b) % N + 1,
        _y = (y * c + z * d) % N + 1,
        x = _x,
        y = _y,
        printf ("%d\n", z);

}