Cod sursa(job #845867)

Utilizator SpiderManSimoiu Robert SpiderMan Data 31 decembrie 2012 18:21:54
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
# include <algorithm>
# include <cstdio>
# include <cassert>
# include <vector>
using namespace std;

# define x first
# define y second

typedef pair <int, int> PR;
const char *FIN = "atac.in", *FOU = "atac.out";
const int MAX = 32005, MAX_L = 16, oo = 0x3f3f3f3f;

vector <PR> G[MAX];
vector <PR> Q;
int N, M, P, lun[MAX << 1], mini[MAX_L + 1][MAX], father[MAX_L + 1][MAX], RMQ[MAX_L + 1][MAX << 2], ap[MAX];
int x, y, a, b, c, d;

void dfs (int S, int T, int L, int val) {
    Q.push_back (make_pair (S, L)), ap[S] = Q.size () - 1;
    mini[0][S] = val, father[0][S] = T;
    for (typeof (G[S].begin ()) it = G[S].begin (); it != G[S].end (); ++it) {
        if (it -> x == T) continue;
        dfs (it -> x, S, L + 1, it -> y);
        Q.push_back (make_pair (S, L));
    }
}

void rmq (void) {
    int size = Q.size () - 1;
    for (int i = 2; i <= size; ++i)
        lun[i] = lun[i >> 1] + 1, RMQ[0][i] = i;
    RMQ[0][1] = 1;
    for (int i = 1; 1 << i < size; ++i)
        for (int j = 1; j <= size - (1 << i); ++j) {
            int k = 1 << (i - 1);
            RMQ[i][j] = RMQ[i - 1][j];
            if (Q[RMQ[i - 1][j + k]].y < Q[RMQ[i][j]].y)
                RMQ[i][j] = RMQ[i - 1][j + k];
        }
}

inline int lca (int x, int y) {
    int st = ap[x], dr = ap[y];
    if (st > dr) swap (st, dr);
    int sol = RMQ[lun[dr - st + 1]][st];
    if (Q[sol].y > Q[RMQ[lun[dr - st + 1]][st + ((dr - st + 1) - (1 << lun[dr - st + 1]))]].y)
        sol = RMQ[lun[dr - st + 1]][st + ((dr - st + 1) - (1 << lun[dr - st + 1]))];
    return Q[sol].x;
}

void solve (void) {
    mini[0][1] = oo;
    for (int i = 1; (1 << i) <= N; ++i)
        for (int j = 1; j <= N; ++j) {
            mini[i][j] = min (mini[i - 1][j], mini[i - 1][father[i - 1][j]]);
            father[i][j] = father[i - 1][father[i - 1][j]];
        }
}

inline int query (int x, int y) {
    if (x == y) return oo;
    int val = Q[ap[x]].y - Q[ap[y]].y, sol = oo;
    for (int i = 0; i < MAX_L; ++i)
        if (val & (1 << i))
            sol = min (sol, mini[i][x]), x = father[i][x];
    return sol;

}

int main (void) {
    assert (freopen (FIN, "r", stdin));
    assert (freopen (FOU, "w", stdout));

    assert (scanf ("%d %d %d", &N, &M, &P) == 3);
    for (int i = 2; i <= N; ++i) {
        assert (scanf ("%d %d", &x, &y) == 2);
        G[i].push_back (make_pair (x, y));
        G[x].push_back (make_pair (i, y));
    }
    Q.push_back (make_pair (0, 0)), dfs (1, 0, 1, 0), rmq (), solve ();
    assert (scanf ("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d) == 6);
    for (int i = 1; i <= M; ++i) {
        int sol = 0;
        if (x != y) {
            int aux = lca (x, y);
            sol = min (query (x, aux), query (y, aux));
        }
        if (i > M - P) printf ("%d\n", sol);
        x = (a * x + b * y) % N + 1;
        y = (c * y + d * sol) % N + 1;
    }
}