Cod sursa(job #795201)

Utilizator mihai995mihai995 mihai995 Data 7 octombrie 2012 19:10:33
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <fstream>
#include <vector>
using namespace std;

const int N = 32005, LG = 15, inf = 0x3f3f3f3f;
int T[LG][N], C[LG][N], doi[2 * N], depth[N], n;

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

struct Muchie{
    int y, c;

    Muchie(){
        c = 0;
    }

    Muchie(int _y, int _c){
        y = _y;
        c = _c;
    }
};

vector<Muchie> graph[N];

struct LowestCommonAncestor{
    int rmq[1 + LG][2 * N], euler[2 * N], start[N], n, size;
    vector<Muchie>* graph;

    inline void sch(int& a, int& b){
        int c = a;
        a = b;
        b = c;
    }

    inline int best(int x, int y){
        return depth[x] < depth[y] ? x : y;
    }

    void dfs(int x){
        rmq[0][++size] = x;
        start[x] = size;

        for (vector<Muchie> :: iterator it = graph[x].begin() ; it != graph[x].end() ; it++){
            depth[it -> y] = 1 + depth[x];
            T[0][it -> y] = x;
            C[0][it -> y] = it -> c;
            dfs(it -> y);
            rmq[0][++size] = x;
        }
    }

    void compute(){
        size = 0;

        dfs(1);

        for (int i = 1 ; i <= LG ; i++)
            for (int j = 1 ; j <= size ; j++)
                rmq[i][j] = best(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1) )]);

        for (int i = 1, j = 0 ; i <= size ; i <<= 1, j++)
            doi[i] = j;

        for (int i = 1 ; i <= size ; i++)
            if (!doi[i])
                doi[i] = doi[i - 1];
    }

    inline void assign_tree(vector<Muchie>* tree, int _n){
        graph = tree;
        n = _n;

        compute();
    }

    inline int lca(int x, int y){
        x = start[x]; y = start[y];

        if (x > y)
            sch(x, y);

        int L = doi[y - x + 1];

        return best(rmq[L][x], rmq[L][y - (1 << L) + 1]);
    }
} LCA;

inline int min(int a, int b){
    return a < b ? a : b;
}

void compute(){
    LCA.assign_tree(graph, n);

    for (int i = 1 ; i < LG ; i++)
        for (int j = 1 ; j <= n ; j++){
            T[i][j] = T[i - 1][ T[i - 1][j] ];
            C[i][j] = min(C[i - 1][j], C[i - 1][ T[i - 1][j] ]);
        }
}

inline int bomb(int x, int L){
    int rez = inf;

    for (int i = doi[L] ; i >= 0 ; i--)
        if (L >= (1 << i)){
            rez = min(rez, C[i][x]);
            L -= 1 << i;
            x = T[i][x];
        }

    return rez;
}

int solve(int x, int y){
    int L = depth[LCA.lca(x, y)];

    return min(bomb(x, depth[x] - L), bomb(y, depth[y] - L));
}

int main(){
    int m, p, r, x, y, A, B, C, D;
    in >> n >> m >> p;

    for (int i = 2 ; i <= n ; i++){
        in >> x >> y;
        graph[x].push_back(Muchie(i, y));
    }

    compute();

    in >> x >> y >> A >> B >> C >> D;

    while (m--){
        r = x != y  ? solve(x, y) : 0;

        if (m < p)
            out << r << "\n";

        x = (A * x + B * y) % n + 1;
        y = (C * y + D * r) % n + 1;
    }

    return 0;
}