Cod sursa(job #1751058)

Utilizator NinjaCubeMihai Radovici NinjaCube Data 31 august 2016 17:33:23
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <fstream>
#include <vector>
#define DIM 66000
#define INF 1000000000
#define MAXLOG 15
using namespace std;
int D[MAXLOG+1][DIM];
int S[MAXLOG+1][DIM];
int niv[DIM];
vector<pair<int, int> > L[DIM];
pair<int, int> t[DIM];
int n, m, p, a, b, c, d, x, y, z, u, v, maxnv;
void dfs(int nod, int nv) {
    niv[nod] = nv;
    maxnv = max(maxnv, nv);
    for (int i=0;i<L[nod].size(); i++) {
        int vec = L[nod][i].first;
        int cost = L[nod][i].second;
        if (niv[ vec ] == 0) {
            t[vec] = make_pair( nod, cost );
            dfs(vec, nv+1);
        }
    }
}
int main () {
    ifstream fin ("atac.in");
    ofstream fout("atac.out");
    fin>>n>>m>>p;
    for (int i=2;i<=n;i++) {
        fin>>u>>v;
        L[i].push_back(make_pair(u,v));
        L[u].push_back(make_pair(i,v));}
    fin>>x>>y>>a>>b>>c>>d;
    dfs(1, 1);
    int aux = maxnv, LG = 0;
    while (aux) {
        aux /= 2;
        LG++;}
    for (int i=0;i<=LG;i++)
        S[i][1] = D[i][1] = INF;
    for (int i=2;i<=n;i++) {
        D[0][i] = t[i].second;
        S[0][i] = t[i].first;}
    for (int log=1; log <=LG; log++)
        for (int i=2;i<=n;i++) {
            if ((1 << log) <= niv[i]) { // S[log][i] = al 2^log stramos al lui i
                S[log][i] = S[ log-1 ][ S[ log-1 ][i] ];
                D[log][i] = min(D[log-1][i], D[log-1][ S[log-1][i] ]);
            } else {
                D[log][i] = INF;
                S[log][i] = INF;}}
    for (int pas = m; pas--;) {
        int log = LG;
        int f = x;
        int g = y;
        int z = INF;
        while (niv[f] != niv[g]) {
            if (niv[f] > niv[g]) {
                if (S[log][f] != INF && niv[ S[log][f] ] >= niv[g]) {
                    z = min(z, D[log][f]);
                    f = S[log][f];
                }
            } else {
                if (S[log][g] != INF && niv[ S[log][g] ] >= niv[f]) {
                    z = min(z, D[log][g]);
                    g = S[log][g];}}
            log--;
        }
        if (f != g) {
            log = LG;
            while (S[0][f] != S[0][g]) {

                if (S[log][f] != S[log][g]) {
                    z = min(z, D[log][f]);
                    z = min(z, D[log][g]);
                    f = S[log][f];
                    g = S[log][g];
                }
                log --;
            }
            z = min(z, D[0][f]);
            z = min(z, D[0][g]);

        }
        if (z ==INF)
            z = 0;

        if (pas < p) {
            fout<<z<<"\n";
        }
        int x1 = (x*a + y*b) % n + 1;
        int y1 = (y*c + z*d) % n + 1;
        x = x1;
        y = y1;
    }

    return 0;
}