Cod sursa(job #1213751)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 28 iulie 2014 22:11:34
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int N,M,P;
int A,B,C,D,X,Y,Result[500005];
vector <int> G[32005],G1[32005];
vector <int> Cost[32005];
int Min[25][32005],Father[25][32005],level;
bool Use2[32005],Use[32005];
int ind,First[32005],Level[32005<<1],counter;
int minimum_result[25][32005<<2],log[32005<<1],Log2[32005];
void Read()
{
    f>>N>>M>>P;
    for(int i=0;i<=20;i++)
        for(int j=0;j<=32000;j++)
            Min[i][j]=(1<<30);
    int i;
    for(i=2;i<=N;i++)
    {
        int U,V;
        f>>U>>V;
        G1[U].push_back(i);
        G1[i].push_back(U);
        Cost[i].push_back(V);
        Cost[U].push_back(V);
    }
    f>>X>>Y>>A>>B>>C>>D;
}
void DFS1(int node)
{
    Use2[node]=1;
    for(int i=0;i<G1[node].size();i++)
    {
        int neighbour=G1[node][i],cost=Cost[node][i];
        if(Use2[neighbour]==0)
        {
            G[node].push_back(neighbour);
            Father[0][neighbour]=node;
            Min[0][neighbour]=cost;
            DFS1(neighbour);
        }
    }
}

void Calculate_log2()
{
    int i=2,next=2;
    while(i<=ind)
    {
        if(i!=next)
            log[i]=log[i-1];
        else
        {
            log[i]=log[i-1]+1;
            next=i*2;
        }
        i++;
    }
}
void Build_matrichs()
{
    int i,j,forward=1;
    for(i=1;i<=log[ind];i++)
    {
        for(j=1;j<=ind-forward*2+1;j++)
        {
            if(Level[minimum_result[i-1][j]]<Level[minimum_result[i-1][j+forward]])
                minimum_result[i][j]=minimum_result[i-1][j];
            else
                minimum_result[i][j]=minimum_result[i-1][j+forward];
        }
        forward*=2;
    }
}
int RMQ(int x,int y)
{
    int i;
    int how_much=log[y-x+1];
    if(log[y-x]==how_much-1)
        return minimum_result[log[y-x+1]][x];
    else
    {
        if(Level[minimum_result[how_much][x]]<Level[minimum_result[how_much][y-(1<<how_much)+1]])
            return minimum_result[how_much][x];
        else
            return minimum_result[how_much][y-(1<<how_much)+1];
    }
}
void DFS(int nod)
{
    minimum_result[0][++ind]=nod;
    if(Use[nod]==0)
        First[nod]=ind,counter++;
    Use[nod]=1;
    Level[nod]=level;
    level++;
    for(unsigned int i=0;i<G[nod].size();i++)
    {
        int vecin=G[nod][i];
        if(Use[vecin]==0)
        {
            DFS(vecin);
            if(counter<N)
                minimum_result[0][++ind]=nod;
        }
    }
    level--;
}
void Precalculate()
{
    for(int i=1;(1<<i)<=N;i++)
        for(int j=1;j<=N;j++)
            Father[i][j]=Father[i-1][Father[i-1][j]];
    for(int i=1;(1<<i)<=N;i++)
        for(int j=1;j<=N;j++)
            Min[i][j]=min(Min[i-1][j],Min[i-1][Father[i-1][j]]);
     for(int i=2;i<=N;i++)
        Log2[i]=Log2[i/2]+1;
}
int minResult(int x,int y)
{
    int dist=Level[x]-Level[y];
    int result=(1<<30);
    while(dist>0)
    {
        int k=Log2[dist];
        result=min(result,Min[k][x]);
        x=Father[k][x];
        dist-=(1<<k);
    }
    return result;
}

void Browse()
{
    int i;
    int x=X,y=Y;
    for(i=1;i<=M;i++)
    {
        int aux1=x,aux2=y;
        if(First[x]>First[y])
            swap(x,y);
        int lca=RMQ(First[x],First[y]);
        int Z=min(minResult(x,lca),minResult(y,lca));
        Result[i]=Z;
        x=((1LL*aux1*A)%N+(1LL*aux2*B)%N)%N+1;
        y=((1LL*aux2*C)%N+(1LL*Z*D)%N)%N+1;
    }
}
int main()
{
    Read();
    DFS1(1);
    DFS(1);
    Calculate_log2();
    Build_matrichs();
    Precalculate();
    Browse();
    for(int i=M-P+1;i<=M;i++)
        g<<Result[i]<<"\n";
    return 0;
}