Cod sursa(job #1211151)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 22 iulie 2014 01:22:45
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.72 kb
#include <iostream>
#include <iomanip>
#include <fstream>

#include <algorithm>
#include <bitset>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif

#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>

#define st first
#define nd second

using namespace std;

typedef long long int64;

ifstream in("atac.in");
ofstream out("atac.out");

const int NMAX = 32010, LOG2NMAX = 16, inf = 0x3f3f3f3f;

int N, P, M, X, Y, A, B, C, D;
int euler[2 * NMAX], RMQ[2 * NMAX][LOG2NMAX], first[NMAX], level[2 * NMAX], ancestor[LOG2NMAX][NMAX], node_level[NMAX], father[NMAX], cost[NMAX], best[LOG2NMAX][NMAX];

bool visited[NMAX];

vector<pair<int, int> > G[NMAX];

void DF(const int node, const int lvl) {
    visited[node] = true;
    euler[++euler[0]] = node;
    level[++level[0]] = lvl;
    first[node] = euler[0];
    node_level[node] = lvl;

    for (size_t it = 0; it < G[node].size(); ++it) {
        if (visited[G[node][it].st]) continue;
        father[G[node][it].st] = node;
        cost[G[node][it].st] = G[node][it].nd;
        DF(G[node][it].st, lvl + 1);
        euler[++euler[0]] = node;
        level[++level[0]] = lvl;
    }
}

void Compute_RMQ() {
    int i, j;
    for (i = 1; i <= euler[0]; ++i) RMQ[i][0] = i;

    for (i = 1; (1 << i) <= euler[0]; ++i)
        for (j = 1; j + (1 << i) - 1 <= euler[0]; ++j)
            if (level[RMQ[j][i - 1]] < level[RMQ[j + (1 << (i - 1))][i - 1]]) RMQ[j][i] = RMQ[j][i - 1];
            else RMQ[j][i] = RMQ[j + (1 << (i - 1))][i - 1];
}

#undef st
#undef nd
int LCA(int st, int nd) {
    st = first[st], nd = first[nd];
    if (st > nd) swap(st, nd);

    int lg2 = -1, value;
    for (value = nd - st + 1; value; value >>= 1, ++lg2);

    if (level[RMQ[st][lg2]] < level[RMQ[nd - (1 << lg2) + 1][lg2]])
        return euler[RMQ[st][lg2]];
    return euler[RMQ[nd - (1 << lg2) + 1][lg2]];
}

#define st first
#define nd second

void Build_ancestor() {
    int i, j;
    for (i = 1; i <= N; ++i) ancestor[0][i] = father[i], best[0][i] = cost[i];

    for (i = 1; (1 << i) < N; ++i)
        for (j = 1; j <= N; ++j) {
            ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
            best[i][j] = min(best[i - 1][j], best[i - 1][ancestor[i - 1][j]]);
        }
}

int main() {
    int i, j, cost;
    in >> N >> P >> M;

    for (i = 2; i <= N; ++i) {
        in >> j >> cost;
        G[i].push_back(make_pair(j, cost));
        G[j].push_back(make_pair(i, cost));
    }

    DF(1, 0);
    Compute_RMQ();
    Build_ancestor();

    cerr << LCA(3, 7);

    in >> X >> Y >> A >> B >> C >> D;

    for (i = 1; i <= P; ++i) {
        int res = inf, node = LCA(X, Y), value = node_level[X] - node_level[node], go = X;

        for (int bit = 0; value && bit < (node_level[X] - node_level[node]); ++bit)
            if ((1 << bit) & value) {
                res = min(res, best[bit][go]);
                go = ancestor[bit][go];
                value -= (1 << bit);
            }

        value = node_level[Y] - node_level[node], go = Y;
        for (int bit = 0; value && bit < (node_level[Y] - node_level[node]); ++bit)
            if ((1 << bit) & value) {
                res = min(res, best[bit][go]);
                go = ancestor[bit][go];
                value -= (1 << bit);
            }
        if (i > P - M) out << res << '\n';
        int _X = (X * A + Y * B) % N + 1;
        int _Y = (Y * C + res * D) % N + 1;
        X = _X, Y = _Y;
    }

    in.close(), out.close();
    return 0;
}