Cod sursa(job #1348867)

Utilizator retrogradLucian Bicsi retrograd Data 19 februarie 2015 21:29:32
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;
typedef int var;

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

const var MAXN = 240002;

struct Edge {
    var n, c;
    Edge(var x, var y) {
        n = x;
        c = y;
    }
};

vector<Edge> A[MAXN];

vector<var> EULER, DEPTH;
var B[MAXN], D[MAXN], PARENT[32][MAXN], MIN[32][MAXN];
var n, k, p;
var LOG[MAXN];



void euler(var node) {
    for(vector<Edge>::iterator it = A[node].begin(); it != A[node].end(); ++it) {
        Edge &e = *it;
        if(e.n == PARENT[0][node]) continue;
        PARENT[0][e.n] = node;
        MIN[0][e.n] = e.c;
        D[e.n] = D[node] + 1;
        euler(e.n);
    }
}

void build_min_table() {
    for(var i=1; (1<<i)<=n; i++) {
        for(var j=1; j<=n; j++) {
            PARENT[i][j] = PARENT[i-1][PARENT[i-1][j]];
            MIN[i][j] = min(MIN[i-1][j], MIN[i-1][PARENT[i-1][j]]);
        }
    }
}

inline var zeros(var d) {
    return d & (-d);
}

var lca(var node1, var node2) {
    var &d1 = D[node1], &d2 = D[node2];
    var delta = d2-d1;
    var minn = 1000001;

    if(node1 == node2) return 0;

    while(delta>0) {
        var t = LOG[zeros(delta)];
        delta -= zeros(delta);
        minn = min(minn, MIN[t][node2]);
        node2 = PARENT[t][node2];

    }
    delta = d1-d2;
    while(delta>0) {
        var t = LOG[zeros(delta)];
        delta -= zeros(delta);
        minn = min(minn, MIN[t][node1]);
        node1 = PARENT[t][node1];

    }

    if(node1 == node2) return minn;

    for(var i=LOG[D[node1]]; i>=0; i--) {
        if(PARENT[i][node1] && PARENT[i][node1] != PARENT[i][node2]) {
            minn = min(minn, MIN[i][node1]);
            minn = min(minn, MIN[i][node2]);
            node1 = PARENT[i][node1];
            node2 = PARENT[i][node2];
        }
    }

    minn = min(minn, MIN[0][node1]);
    minn = min(minn, MIN[0][node2]);

    return minn;
}

var build_log_table(var maxx) {
    for(var i=2; i<=maxx; i++) {
        LOG[i] = LOG[i/2] + 1;
    }
}



int main() {
    var t, c;
    fin>>n>>k>>p;
    for(var i=2; i<=n; i++) {
        fin>>t>>c;
        A[t].push_back(Edge(i, c));
        A[i].push_back(Edge(t, c));
        //EDGES.push_back(FullEdge(i, t, c));
    }
    euler(1);
    build_min_table();
    build_log_table(n+1);

    var x, y, a, b, d;

    fin>>x>>y>>a>>b>>c>>d;
    for(var i=1; i<=k; i++) {
        var rez = lca(x, y);
        x = (x*a + y*b)%n + 1;
        y = (y*c + rez*d)%n + 1;
        if(i > k-p) {
            fout<<rez<<'\n';
        }
    }




    return 0;
}