Cod sursa(job #1033421)

Utilizator smaraldaSmaranda Dinu smaralda Data 16 noiembrie 2013 21:50:02
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 32000,INF = 2e9;

bool vis[NMAX +5];
vector <int> arb[NMAX + 5],bombe[NMAX + 5];
int n,lvl[NMAX + 5],stramos[20][NMAX + 5],cst[20][NMAX + 5];

void dfs (int nod, int tata, int b) {
    stramos[0][nod] = tata;
    cst[0][nod] = b;
    lvl[nod] = lvl[tata] + 1;
    vis[nod] = 1;
    for(int i = 0; i < arb[nod].size(); i++)
        if(!vis[arb[nod][i]])
            dfs(arb[nod][i],nod,bombe[nod][i]);
}

int LCA (int x, int y) {
    if(x == y)
        return x;
    int p;
    for(p = 0; stramos[p][x] != stramos[p][y]; p++);
    if(p)
        p--;
    return LCA(stramos[p][x],stramos[p][y]);
}

int urca (int x, int niv) {
    if(niv == 0)
        return x;
    int p;
    for(p = 0; (1<<p) <= niv; p++);
    if(p)
    p--;
    return urca(stramos[p][x],niv - (1<<p));
}

int cost (int x, int niv) {
    if(niv == 0)
        return INF;
    int p,res = INF;
    for(p = 0; (1<<p) <= niv; p++);
    for(; p >=0; p--)
        if((1<<p) <= niv) {
            res = min(res,cst[p][x]);
            x = stramos[p][x];
            niv = niv - (1<<p);
            }
    return res;
}

int query (int x, int y) {
    int resx,resy,lca;
    if(x == y)
        return 0;
    resx = resy = INF;
    if(lvl[x] < lvl[y]) {
        resy = min(resy,cost(y, lvl[y] - lvl[x]));
        y = urca(y, lvl[y] - lvl[x]);
        }
    if(lvl[y] < lvl[x]) {
        resx = min(resy,cost(x, lvl[x] - lvl[y]));
        x = urca(x, lvl[x] - lvl[y]);
        }
    lca = LCA(x,y);
    resx = min(resx,cost(x,lvl[x] - lvl[lca]));
    resy = min(resy,cost(y,lvl[y] - lvl[lca]));
    return min(resx,resy);
}

int main() {
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    int flag,j,nx,ny,nz,x,p,y,z,b,c,d,m,i,a;
    scanf("%d%d%d",&n,&m,&p);
    for(i = 2; i <= n; i++) {
        scanf("%d%d",&a,&b);
        arb[i].push_back(a);
        arb[a].push_back(i);
        bombe[i].push_back(b);
        bombe[a].push_back(b);
        }
    scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);

    dfs(1,0,INF);

    for(i = 1; (1<<i) <= n; i++)
        for(j = 1; j <= n; j++) {
            stramos[i][j] = stramos[i - 1][stramos[i - 1][j]];
            cst[i][j] = min(cst[i - 1][j], cst[i - 1][stramos[i - 1][j]]);
            }

    z = query(x,y);
    for(i = 2; i <= m; i++) {
        nx = (x * a + y * b) % n + 1;
        ny = (y * c + z * d) % n + 1;
        z = query(nx,ny);
        if(m - p + 1 <= i)
            printf("%d\n",z);
        x = nx;
        y = ny;
        }
    return 0;
}