Cod sursa(job #1537619)

Utilizator algebristulFilip Berila algebristul Data 27 noiembrie 2015 16:40:29
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>

#define FILEIN "atac.in"
#define FILEOUT "atac.out"

using namespace std;

const int NMAX = 32005; // log = 15
const int INF = 0x3f3f3f3f;

int cnt = 0;
int n, p, m;
int x, y, a, b, c, d;
vector<pair<int, int> > A[NMAX];
int P[NMAX][15];
int M[NMAX][15];
int D[NMAX];
int Uz[NMAX];
int First[NMAX];
int Last[NMAX];
int Euler[NMAX * 2 + 1];
int RMQ[NMAX * 2 + 1][15];
int LG[NMAX * 2 + 1];

void dfs(int x) {
    Uz[x] = 1;
    First[x] = ++cnt;
    Last[x] = cnt;
    Euler[cnt] = x;

    for (int i = 0; i < A[x].size(); i++) {
        int y = A[x][i].first;
        if (Uz[y])
            continue;
        int c = A[x][i].second;
        P[y][0] = x;
        M[y][0] = c;
        for (int j = 1; ; j++) {
            P[y][j] = P[P[y][j-1]][j-1];
            if (!P[y][j])
                break;
            M[y][j] = min(M[y][j], M[P[y][j-1]][j-1]);
        }
        D[y] = D[x] + 1;
        Uz[y] = 1;
        dfs(y);

        Last[x] = ++cnt;
        Euler[cnt] = x;
    }
}

int lca(int x, int y) {
    int a = min(First[x], First[y]);
    int b = max(First[x], First[y]);

    int len = LG[b - a + 1];

    if (D[RMQ[a][len]] < D[RMQ[b - (1 << len) + 1][len]])
        return RMQ[a][len];

    return RMQ[b - (1 << len) + 1][len];
}

void process() {
    D[1] = 1;
    memset(M, INF, sizeof(M));
    dfs(1);

    for (int i = 2; i <= NMAX * 2; i++) {
        LG[i] = LG[i/2] + 1;
    }

    for (int i = 1; i <= n * 2; i++) {
        RMQ[i][0] = Euler[i];
    }

    for (int j = 1; j < 15; j++) {
        for (int i = 1; i + (1 << (j-1)) <= n * 2; i++) {
            if (D[RMQ[i][j - 1]] < D[RMQ[i + (1 << (j-1))][j - 1]])
                RMQ[i][j] = RMQ[i][j-1];
            else
                RMQ[i][j] = RMQ[i + (1 << (j-1))][j-1];
        }
    }
}

int tree_min(int x, int ancestor) {
    int diff = D[x] - D[ancestor];

    int ans = INF;

    while (diff) {
        ans = min(ans, M[x][LG[diff]]);
        diff -= diff & (-diff);
    }

    if (ans == INF)
        return 0;
    return ans;
}

int query(int x, int y) {
    int t = lca(x, y);
    if (x == y)
        return 0;
    if (t == x)
        return tree_min(y, t);
    if (t == y)
        return tree_min(x, t);
    return min(tree_min(x, t), tree_min(y, t));
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    cin >> n >> m >> p;
    for (int i = 2; i <= n; i++) {
        cin >> x >> c;
        A[x].push_back(make_pair(i, c));
        A[i].push_back(make_pair(x, c));
    }

    process();

    cin >> x >> y >> a >> b >> c >> d;

    for (int i = 1; i <= m; i++) {
        int z = query(x, y);

        x = (x * a + y * b) % n + 1;
        y = (y * c + z * d) % n + 1;

        if (i >= m - p + 1) {
            cout << z << '\n';
        }
    }


    return 0;
}