Cod sursa(job #912795)

Utilizator ericptsStavarache Petru Eric ericpts Data 12 martie 2013 19:23:40
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <vector>
using namespace std;
struct edge{
    int to,cost;
};
#define maxn 32005
#define pb push_back
#define forEach(G) for( typeof(G.begin()) it = G.begin() ; it != G.end() ; ++ it )
vector<edge> G[maxn];
ifstream in("atac.in");
ofstream out("atac.out");
int n,m,p;
int RMQ[17][maxn*2];
int ancestor[17][maxn];
int dest[17][maxn];
int first[maxn];
int root[maxn];
int cost[maxn];
int eul[maxn*2],H[maxn*2];
int CR;
int lg[maxn*2];
bool viz[maxn];

void dfs(const int &nod,const int &lev)
{
    viz[nod]=1;

    eul[++CR] = nod;
    first[nod]=CR;
    H[CR]=lev;

    forEach(G[nod]){
        if(!viz[it->to]){
            dfs(it->to,lev+1);
            root[it->to]=nod;
            cost[it->to]=it->cost;
        }

        eul[++CR]=nod;
        H[CR]=lev;

    }
}

void build_RMQ()
{
    int i,j,l;
    for(i=2;i<=CR;++i)
        lg[i] = lg[i/2]+1;
    for(i=1;i<=CR;++i)
        RMQ[0][i]=i;
    for(i=1;(1 << i) < CR;++i){
        for(j=1; j <= CR - (1 << i); ++ j ){
            l = 1 << (i-1);
            RMQ[i][j] = RMQ[i-1][j];
            if(H[RMQ[i-1][j+l]] < H[RMQ[i][j]])
                RMQ[i][j] = RMQ[i-1][j+l];
        }
    }
}
int LCA(int x,int y)
{
    x = first[x],y = first[y];
    if(x > y)
        swap(x,y);
    int diff = y-x+1,l = lg[diff],sol;
    sol = RMQ[l][x];
    diff -= 1 << l;
    if(H[RMQ[l][x+diff]] < H[sol])
        sol = RMQ[l][x+diff];
    return H[sol];

}

void precalc()
{
    int i,j;
    for(i=1;i<=n;++i){
        ancestor[0][i] = root[i];
        dest[0][i] = cost[i];
    }
    for(i=1;(1<<i)<=n;++i){
        for(j=1;j<=n;++j){
            ancestor[i][j] = ancestor[i-1][ancestor[i-1][j]];
            dest[i][j] = min(dest[i-1][j],dest[i-1][ancestor[i-1][j]]);
        }
    }
}

int query(int nod,int cat){
    int ret = 1 << 30;
    for(int i = 0 ; cat; ++i){
        if(cat & (1 << i)){
            ret = min(ret,dest[i][nod]);
            nod = ancestor[i][nod];
            cat ^= 1 << i;
        }
    }return ret;
}

int solve(int a,int b)
{
    if(a==b)return 0;
    int mid = LCA(a,b),Ha,Hb;
    Ha = H[first[a]] - H[mid];
    Hb = H[first[b]] - H[mid];
    return min(query(a,Ha),query(b,Hb));
    return 1;
}

int main()
{
    int i,a,b;
    int X,Y,A,B,C,D;
    in >> n >> m >> p;
    for(i=2;i<=n;++i){
        in >> a >> b;
        G[i].pb({a,b});
        G[a].pb({i,b});
    }in >> X >> Y >> A >> B >> C >> D;
    dfs(1,1);
    build_RMQ();
    precalc();
    int val;
    for(i=1;i<=m;++i){
        val = solve(X,Y);
        X = ( X*A +   Y*B )%n + 1;
        Y = ( Y*C + val*D )%n + 1;
        if(m-i < p)
            out << val << "\n";
    }
    return 0;
}