Cod sursa(job #1738914)

Utilizator mariusn01Marius Nicoli mariusn01 Data 8 august 2016 01:03:46
Problema Atac Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <fstream>
#include <vector>
#define DIM 66000
#define INF 1000000000

using namespace std;

int D[17][DIM]; //D[i][j] cea mai mica muchie considerand deasupra nodului j 2^i muchii
int S[17][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;

void dfs(int nod, int nv) {
    niv[nod] = 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);

    for (int i=0;i<=16;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 <=16; 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--;) {

        // muchia minima pe drumul de la x la y
        int log = 16;
        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 = 16;
            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 (pas < p)
            fout<<(z != INF ? z : 0)<<"\n";

        int x1 = (x*a + y*b) % n + 1;
        int y1 = (y*c + z*d) % n + 1;
        x = x1;
        y = y1;
    }

    return 0;
}