Cod sursa(job #1419572)

Utilizator tudi98Cozma Tudor tudi98 Data 15 aprilie 2015 22:58:42
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
using namespace std;
#define Nmax 32005
#define logNmax 20
#define inf 0x3f3f3f3f

long long N,M,P,A,B,C,D,X,Y;
vector< pair<int,int> > Adj[Nmax];
int T[logNmax][Nmax];
int dp[logNmax][Nmax];
int L[Nmax];

void dfs(int s)
{
    for(auto p: Adj[s]) {
        if(T[0][s] == p.first) continue;
        L[p.first] = L[s] + 1;
        T[0][p.first] = s;
        dp[0][p.first] = p.second;
        dfs(p.first);
    }
}

void build_LCA()
{
    for(int k = 1; (1 << k) <= N; k++)
        for(int i = 1; i <= N; i++)
            T[k][i] = T[k-1][T[k-1][i]];
}

void build_dp()
{
    for(int k = 1; (1 << k) <= N; k++)
        for(int i = 1; i <= N; i++)
            dp[k][i] = min(dp[k-1][i],dp[k-1][T[k-1][i]]);          // dp[k][i] = cel mai mic element de pe lantul
                                                                    //            dintre i si al 2^k - lea stramos  
}

int lca(int x,int y)
{
    if(L[x] < L[y])
        swap(x,y);
    
    int log1,log2;
    for(log1 = 0; log1 < L[x]; log1++);
    for(log2 = 0; log2 < L[y]; log2++);

    for(int k = log1; k >= 0; k--)
        if(L[x] - (1 << k) >= L[y])
            x = T[k][x];

    if(x == y) return x;

    for(int k = log2; k >= 0; k--)
        if(T[k][x] != T[k][y] && T[k][x] != 0) {
            x = T[k][x];
            y = T[k][y];
        }

    return T[0][x];
}

int k_th_Ancestor(int x,int k)
{
    int log;
    for(log = 0; (1 << log) < k; log++);

    for(int j = log; j >= 0 && k; j--)
        if(k >= (1 << j)) {
            k -= (1 << j);
            x = T[j][x];
        }
    
    return x;
}

int rmq(int x,int y)           // on chain x,y
{
    if(x == y) return inf;

    if(L[x] < L[y])
        swap(x,y);

    int k;
    for(k = 0; (1 << k) <= L[x] - L[y]; k++);
    k--;

    int mid = k_th_Ancestor(x,L[x] - L[y] - (1 << k));

    if(dp[k][x] > dp[k][mid])
        return dp[k][mid];
    return dp[k][x];
}

int query(int x,int y)
{
    if(x == y) return 0;
    int l = lca(x,y);
    return min(rmq(l,x),rmq(l,y));
}

int main()
{
    ifstream fin("atac.in");
    ofstream fout("atac.out");

    fin >> N >> M >> P;
    for(int i = 2; i <= N; i++) {
        int u,v;
        fin >> u >> v;
        Adj[i].push_back(make_pair(u,v));
        Adj[u].push_back(make_pair(i,v));
    }

    fin >> X >> Y >> A >> B >> C >> D;

    L[1] = 1;
    dfs(1);
    build_LCA();
    build_dp();

    for(long long i = 1, Z = query(X,Y); i <= M; i++) {
        if(i >= M - P + 1)
            fout << Z << "\n";

        X = (X*A + Y*B)%N + 1;
        Y = (Y*C + Z*D)%N + 1; 
        Z = query(X,Y); 
    }
}