Cod sursa(job #1348789)

Utilizator retrogradLucian Bicsi retrograd Data 19 februarie 2015 21:01:47
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 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;



void euler(var node) {
    EULER.push_back(node);
    DEPTH.push_back(D[node]);
    B[node] = EULER.size() - 1;

    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);
        EULER.push_back(node);
        DEPTH.push_back(D[node]);
    }
}

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

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 find_min(var son, var parent) {
    var d1 = D[son], d2 = D[parent];
    var levels = d1 - d2;
    var mmm = 10000001;
    while(levels) {
        var d = LOG[zeros(levels)];
        mmm = min(mmm, MIN[d][son]);
        son = PARENT[d][son];
        levels -= zeros(levels);
    }
    return mmm;
}


var RMQ[32][MAXN], SOL[32][MAXN];
void build_table(var nm) {

    for(var i=1; i<=nm; i++) {
        RMQ[0][i] = DEPTH[i];
        SOL[0][i] = EULER[i];
    }

    for(var i=1; (1<<i) <= nm; i++) {
        for(var j=1; j+(1<<i)-1 <= nm; j++) {
            if(RMQ[i-1][j] < RMQ[i-1][j+(1<<(i-1))]) {
                RMQ[i][j] = RMQ[i-1][j];
                SOL[i][j] = SOL[i-1][j];
            } else {
                RMQ[i][j] = RMQ[i-1][j+(1<<(i-1))];
                SOL[i][j] = SOL[i-1][j+(1<<(i-1))];
            }
        }
    }
}

var rmq(var b, var e) {
    var len = LOG[e-b+1];
    if(RMQ[len][b] < RMQ[len][e-(1<<len)+1]) {
        return SOL[len][b];
    } else {
        return SOL[len][e-(1<<len)+1];
    }
}

var lca(var n1, var n2) {
    if(B[n1] < B[n2]) {
        return rmq(B[n1], B[n2]);
    } else {
        return rmq(B[n2], B[n1]);
    }
}



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.push_back(0);
    DEPTH.push_back(0);
    euler(1);

    /*for(var i=0; i<EULER.size(); ++i) {
        fout<<EULER[i]<<" ";
    }
    fout<<endl;
    for(var i=0; i<EULER.size(); ++i) {
        fout<<DEPTH[i]<<" ";
    }
    fout<<endl;
*/

    build_log_table(EULER.size());
    build_table(EULER.size() - 1);
    build_min_table();
/*
    for(var i=0; (1<<i) <= n; i++) {
        for(var j=1; j<=n; j++) {
            fout<<MIN[i][j]<<" ";
        }
        fout<<endl;
    }
*/

    //fout<<lca(8, 6);




    var x, y, a, b, d;


    //fout<<find_min(10, 5);

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




    return 0;
}