Cod sursa(job #2077939)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 28 noiembrie 2017 19:06:45
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <vector>
#define ff first
#define ss second
#define INF 2e9
#define DIM 32002

using namespace std;

ifstream f("atac.in");
ofstream g("atac.out");

int n, m, p, a, b, c, D,  putere, put[DIM], Niv[DIM], viz[DIM], x, y, val;
pair<int, int> d[20][DIM];

vector<pair<int, int> > arb[DIM];

void dfs(int nod, int niv){
    viz[nod] = 1;
    for(int i = 0; i < arb[nod].size(); ++ i){
        pair<int, int> nodc = arb[nod][i];
        if(!viz[nodc.ff]){
            d[0][nodc.ff] = make_pair(nod, nodc.ss);
            Niv[nodc.ff] = niv;
            dfs(nodc.ff, niv + 1);
        }
    }
}

void pow(){
    for(int i = 2; i <= n; ++ i)
        put[i] = put[i / 2] + 1;
}

int lca(int x, int y){
    if(Niv[y] < Niv[x])
        swap(x, y);
    int dif = Niv[y] - Niv[x];
    while(dif){
        putere = put[dif];
        y = d[putere][y].ff;
        dif -= (1 << putere);
    }
    if(x == y)
        return x;
    int ok = 1;
    while(x && d[0][x].ff != d[0][y].ff){
        if(ok == 1)
            putere = put[Niv[x]];
        else
            -- putere;
        ok = 0;
        if(d[putere][x].ff != d[putere][y].ff){
            x = d[putere][x].ff;
            y = d[putere][y].ff;
            ok = 1;
        }
        if(x == y)
            return x;
    }
    return  d[0][x].ff;
}

int sol(int x, int y){
    if(x == y)
        return INF;
    if(Niv[y] < Niv[x])
        swap(x, y);
    int dif = Niv[y] - Niv[x];
    int minim = INF;
    while(dif){
        int putere = put[dif];
        minim = min(minim, d[putere][y].ss);
        y = d[putere][y].ff;
        dif -= (1 << putere);
    }
    return minim;
}

int main()
{
    f>>n>>m>>p;
    for(int i = 2; i <= n; ++ i){
        f>>x>>y;
        arb[i].push_back(make_pair(x, y));
        arb[x].push_back(make_pair(i, y));
    }
    f>>x>>y>>a>>b>>c>>D;
    dfs(1, 1);
    pow();
    for(int k = 1; (1 << k) <= n; ++ k)
        for(int i = 1; i <= n; ++ i){
            d[k][i].ff = d[k - 1][d[k - 1][i].ff].ff;
            d[k][i].ss = min(d[k - 1][i].ss, d[k - 1][d[k - 1][i].ff].ss);
        }

    for(int cnt = 1; cnt <= m; ++ cnt){
        int nod = lca(x, y);
        val = min(sol(x, nod), sol(y, nod));
        if(val == INF)
            val = 0;
        if(cnt >= m - p + 1)
            g<<val<<'\n';
        x = (x * a + y * b) % (n + 1);
        y = (y * c + val * D) % (n + 1);
    }

    return 0;
}