Cod sursa(job #998476)

Utilizator smaraldaSmaranda Dinu smaralda Data 17 septembrie 2013 09:36:06
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

#define NMAX 32000
#define INF 0x3f3f3f3f

struct EDGE { int node, b; };

vector <EDGE> arb[NMAX + 5];
bool vis[NMAX + 5];
int p2,lvl[NMAX + 5],pos[NMAX + 5], sz, euler[NMAX * 2 + 10], aint[NMAX * 2 + 10];
vector <int> bombe[NMAX + 5];
int str[20][NMAX + 5], cst[20][NMAX + 5];

EDGE make (int a, int b) {
    EDGE ret = {a,b};
    return ret;
}

void update (int node, int left, int right, int pos, int val) {
    if(left == right) {
        aint[node] = val;
        return;
        }
    aint[node] = min(aint[node],val);
    int mid = (left + right) / 2, leftSon = node * 2, rightSon = node * 2 + 1;
    if(pos <= mid)
        update(leftSon,left,mid,pos,val);
    else
        update(rightSon,mid + 1,right,pos,val);
}

int query (int node, int left, int right, int a, int b) {
    if(a <= left && b >= right)
        return aint[node];
    int ans = INF, mid = (left + right) / 2, leftSon = 2 * node, rightSon = 2 * node + 1;
    if(mid >= a)
        ans = min(ans, query(leftSon,left,mid,a,b));
    if(mid < b)
        ans = min(ans, query(rightSon,mid + 1,right,a,b));
    return ans;
}

void dfs (int node, int tata, int b) {
    vis[node] = 1;
    lvl[node] = lvl[tata] + 1;
    cst[0][node] = b;
    str[0][node] = tata;
    euler[++sz] = node;
    pos[node] = sz;

    for(int i = 0; i < arb[node].size(); i++)
        if(!vis[arb[node][i].node]) {
            dfs(arb[node][i].node,node,arb[node][i].b);
            euler[++sz] = node;
            pos[node] = sz;
            }
}

int cost (int node, int n) {
    int p,ans;
    if(n == 0)
        return 0;
    for(p = 0; (1<<p) <= n; p++);
    ans = INF;
    for(; p >= 0; p--)
        if((1<<p) <= n) {
            ans = min(ans, cst[p][node]);
            node = str[p][node];
            n = n - (1 << p);
            }
    return ans;
}

int q (int x, int y) {
    if(x == y)
        return 0;
    if(pos[x] > pos[y])
        swap(x,y);
    int lca;
    lca = query(1,1,p2,pos[x],pos[y]);
    return min(cost(x,lvl[x] - lca), cost(y,lvl[y] - lca));
}

int main() {
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    int n,j,m,xp,yp,p,i,v,u,x,y,z,a,b,c,d;
    scanf("%d%d%d",&n,&m,&p);
    for(i = 2; i <= n; i++) {
        scanf("%d%d",&u,&v);
        arb[i].push_back(make(u,v));
        arb[u].push_back(make(i,v));
        }
    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++) {
            str[i][j] = str[i - 1][str[i - 1][j]];
            cst[i][j] = min(cst[i - 1][j], cst[i - 1][str[ i - 1][j]]);
            }

    memset(aint,INF,sizeof(aint));
    for(p2 = 1; p2 <= sz; p2 = p2 << 1);
    for(i = 1; i <= sz; i++)
        update(1,1,p2,i,lvl[euler[i]]);

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