Cod sursa(job #1524908)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 14 noiembrie 2015 15:48:29
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include<fstream>
#include<vector>
#include<iostream>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
const int NMAX = 32005;
const int LGMAX = 17;
vector<pair<int,int> > v[NMAX];
int n,m,x,y,a,b,c,d,p,nr,H[2*NMAX],RMQ[LGMAX][2*NMAX],K,F[NMAX],viz[NMAX],D[NMAX],lg[2*NMAX],max_depht;
struct st{

    int m_min;
    int nd;
};
st M[LGMAX][NMAX];

void euler(int nod,int depht){

    viz[nod] = 1;
    H[++K] = nod;
    F[nod] = K;
    D[nod] = depht;
    max_depht = max(max_depht,D[nod]);
    for(vector<pair<int,int> >::iterator it = v[nod].begin() ; it != v[nod].end() ; ++it)
        if(!viz[(*it).first]){

            euler((*it).first,depht + 1);
            H[++K] = nod;
        }
}

void RMQ_calc()
{

    lg[1] = 0;
    for(int i = 2 ; i <= K ; ++i)
        lg[i] = lg[i/2] + 1;
    for(int i = 1 ; i <= K ; ++i)
        RMQ[0][i] = H[i];
    for(int i = 1 ; i <= lg[K] ; ++i)
        for(int j = 1 ; j + (1 << i) - i <= K ; ++j)
            if(D[RMQ[i-1][j+(1 << (i-1))]] < D[RMQ[i-1][j]])
                RMQ[i][j] = RMQ[i-1][j + (1 << (i-1))];
            else
                RMQ[i][j] = RMQ[i-1][j];

}

int LCA(int first,int last)
{

    int unu = F[first];
    int doi = F[last];
    if(unu > doi)
        swap(unu,doi);
    int lung = doi - unu + 1;
    int log = lg[lung];
    int diff = lung - (1 << lg[lung]);
    if(D[RMQ[log][unu]] < D[RMQ[log][unu + diff]])
        return RMQ[log][unu];
    return RMQ[log][unu + diff];

}

void dfs(int nod,int tata,int val)
{

    viz[nod] = 1;
    if(tata == -1)
        M[0][nod].m_min = -1;
    else{
        M[0][nod].m_min = val;
        M[0][nod].nd = tata;
    }
    for(vector<pair<int,int> >::iterator it = v[nod].begin() ; it != v[nod].end() ; ++it)
        if(!viz[(*it).first])
            dfs((*it).first,nod,(*it).second);

}

void calc_min_edge()
{

    for(int i = 1 ; i <= lg[max_depht] ; ++i)
        for(int j = 1  ; j <= n ; ++j)
            if(D[j] >= (1 << i)){
                M[i][j].m_min = min(M[i-1][j].m_min , M[i-1][M[i-1][j].nd].m_min);
                M[i][j].nd = M[i-1][M[i-1][j].nd].nd;
            }
}

int min_edge(int first,int last)
{

    int diff;
    int rez = 1 << 30;
    do{

        diff = D[last] - D[first];
        if(diff != 0){
            rez = min(rez,M[lg[diff]][last].m_min);
            last = M[lg[diff]][last].nd;
        }
    }while(diff != 0);
    return rez;
}

void read()
{

    in>>n>>m>>p;
    int m1,cost;
    for(int i = 1 ; i < n ; ++i){

        in>>m1>>cost;
        v[m1].push_back(make_pair(i + 1,cost));
    }
    in>>x>>y>>a>>b>>c>>d;
    in.close();
}

void solve()
{

    euler(1,0);
    RMQ_calc();
    for(int i = 1 ; i <= n ; ++i)
        viz[i] = 0;
    dfs(1,-1,0);
    calc_min_edge();
    for(int i = 1 ; i <= m ; ++i){

        int lca = LCA(x,y);
        int rez = 1 << 30;
        rez = min(rez,min_edge(lca,x));
        rez = min(rez,min_edge(lca,y));
        if(i >= p)
            out<<rez<<"\n";
        x = ((x * a + y * b) %n ) + 1;
        y = ((y * c + rez * d) % n) + 1;
    }
    out.close();
}

int main()
{

    read();
    solve();
    return 0;
}