Cod sursa(job #1752261)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 3 septembrie 2016 13:15:51
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<fstream>
#include<vector>
#define DIM 32005
using namespace std;
int n, m, k, nr, i, j, ii, jj, x, y, A, B, C, D, p, nod, minim, xa, ya;
int w[2 * DIM], niv2[2 * DIM], d[16][2 * DIM], a[15][DIM], e[15][DIM], b[2 * DIM], first[DIM], ni[DIM];
vector<int> v[DIM];
ifstream fin("atac.in");
ofstream fout("atac.out");
void dfs(int nod, int niv){
    nr++;
    w[nr] = nod;
    niv2[nr] = niv;
    first[nod] = nr;
    ni[nod] = niv;
    for(int i = 0; i < v[nod].size(); i++){
        dfs(v[nod][i], niv + 1);
        nr++;
        w[nr] = nod;
        niv2[nr] = niv;
    }
}
int main(){
    fin>> n >> m >> k;
    for(i = 0; (1 << i) < n; i++){
        for(j = 1; j <= n; j++){
            e[i][j] = 1000000;
        }
    }
    for(i = 2; i <= n; i++){
        fin>> x >> y;
        v[x].push_back(i);
        a[0][i] = x;
        e[0][i] = y;
    }
    dfs(1, 1);
    d[0][1] = 1;
    for(i = 2; i <= nr; i++){
        b[i] = b[i / 2] + 1;
        d[0][i] = i;
    }
    for(i = 1; (1 << i) < nr; i++){
        for(j = 1; j <= nr - (1 << i); j++){
            d[i][j] = d[i - 1][j];
            if(niv2[d[i][j] ] > niv2[ d[i - 1][j + (1 << (i - 1))]]){
                d[i][j] = d[i - 1][j + (1 << (i - 1))];
            }
        }
    }
    for(i = 1; (1 << i) < n; i++){
        for(j = 1; j <= n; j++){
            a[i][j] = a[i - 1][ a[i - 1][j] ];
            e[i][j] = min(e[i - 1][j], e[i - 1][ a[i - 1][j] ]);
        }
    }
    fin>> x >> y >> A >> B >> C >> D;
    for(i = 1; i <= m; i++){
        ii = first[x];
        jj = first[y];
        if(ii > jj){
            swap(ii, jj);
        }
        p = b[jj - ii + 1];
        if(niv2[ d[p][ii] ] < niv2[ d[p][jj - (1 << p) + 1]]){
            nod = d[p][ii];
        }
        else{
            nod = d[p][jj - (1 << p) + 1];
        }
        nod = w[nod];
        minim = 10000000;
        ii = x;
        jj = ni[x] - ni[nod];
        while(jj > 0){
            minim = min(minim, e[ b[jj] ][ii]);
            ii = a[ b[jj] ][ii];
            jj -= (1 << b[jj]);
        }
        ii = y;
        jj = ni[y] - ni[nod];
        while(jj > 0){
            minim = min(minim, e[ b[jj] ][ii]);
            ii = a[ b[jj] ][ii];
            jj -= (1 << b[jj]);
        }
        if(i >= m - k + 1){
            fout<< minim <<"\n";
        }
        xa = (x * A + y * B) % n + 1;
        ya = (y * C + minim * D) % n + 1;
        x = xa;
        y = ya;
    }
    return 0;
}