Cod sursa(job #1197281)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 11 iunie 2014 16:21:05
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.97 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>
#include <cmath>

#define INF 0x3f3f3f3f
#define Nmax 32005

using namespace std;
vector<pair<int,int> > G[Nmax];
vector<int> lantz[Nmax];
vector<int> cost[Nmax]; /// cost[i][j] costul de a ajunge in lantul i de la tatal lui j la j
vector<int> range[Nmax];

bitset<Nmax> used;

int N,M,P,XX,YY,a,b,c,d,ZZ;

int greutate[Nmax]; /// greutatea nodului curent
int adancime[Nmax]; /// adancimea nodului curent
int care[Nmax]; /// in care lantz se afla nodul curent
int pozitie_nod[Nmax]; /// pozitia nodului curent in lantzul sau
int tata_lantz[Nmax]; /// tata lantzului curent
int nrl = 1; /// nr lanturi


class cmp{
public:
    bool operator()(const pair<int,int> A,const pair<int,int> B)const
    {
        return greutate[A.first] > greutate[B.first];
    }
};

void read()
{
    scanf("%d%d%d",&N,&M,&P);
    int x,v;
    for(int i = 1; i < N; ++i)
    {
        scanf("%d%d",&x,&v);
        G[x].push_back(make_pair(i+1,v));
        G[i+1].push_back(make_pair(x,v));
    }
    scanf("%d%d%d%d%d%d",&XX,&YY,&a,&b,&c,&d);
}


void DFSW(int k)
{
    used[k] = 1;
    for(vector<pair<int,int> > :: iterator it = G[k].begin(); it != G[k].end(); ++it)
        if(!used[it->first])
        {
            adancime[it->first] = adancime[k] + 1;
            DFSW(it->first);
        }
    for(vector<pair<int,int> > :: iterator it = G[k].begin(); it != G[k].end(); ++it)
        greutate[k] += greutate[it->first];
    ++greutate[k];
}

void weighing()
{
    for(int i =1; i <= N; ++i)
        sort(G[i].begin(),G[i].end(),cmp());
}
int cost_lantz;

void descomp(int k,int dad)
{
    care[k] = nrl;
    cost[nrl].push_back(cost_lantz);
    lantz[nrl].push_back(k);
    pozitie_nod[k] = lantz[nrl].size() - 1;
    used[k] = 1;
    for(vector<pair<int,int> >::iterator it = G[k].begin(); it != G[k].end(); ++it)
        if(!used[it->first])
        {
            if(lantz[nrl].size() == 1)
                tata_lantz[nrl] = k;
            cost_lantz = it->second;
            descomp(it->first,k);
        }
    if(G[k].size() == 1 && k != 1){
        ++nrl; /// leaf
        lantz[nrl].push_back(0);
        cost[nrl].push_back(0);
    }
}
void descompunere()
{
    used = 0;
    lantz[1].push_back(0);
    cost[1].push_back(0);
    cost_lantz = INF;
    descomp(1,0);
}
void alocare()
{
    for(int i = 1; i <= nrl; ++i)
        for(int j = 0; j <= (1<<((int)log2(lantz[i].size())+ 1)) + 1 ; ++j)
            range[i].push_back(0);
}

void heavy_path_decomposition()
{
    adancime[1] = 1;
    DFSW(1);
    weighing();
    used = 0;
    descompunere();
    --nrl;
    alocare();
}
int line,A,B,pos,answer;

class SegmentTree{
public:
    void Build(int li,int lf,int pz)
    {
        if(li == lf)
        {
            range[line][pz] = cost[line][li];
            return;
        }
        int m = li + ((lf-li)>>1);
        Build(li,m,pz<<1);
        Build(m+1,lf,(pz<<1)|1);
        range[line][pz] = min(range[line][pz<<1],range[line][(pz<<1)|1]);
    }
    void Querry(int li,int lf,int pz)
    {
        if(A <= li && lf <= B)
        {
            answer = min(answer,range[line][pz]);
            return;
        }
        int m = li + ((lf-li)>>1);
        if(A <= m) Querry(li,m,pz<<1);
        if(m < B) Querry(m+1,lf,(pz<<1)|1);
    }
    void Make()
    {
        for(int i = 1; i <= nrl; ++i)
        {
            line = i;
            Build(1,lantz[i].size()-1,1);
        }
    }
}Aint;

void solve()
{
    int _X,_Y,x = XX ,y = YY;
    int savedx,savedy;
    for(int i = 1; i <= M; ++i)
    {
        answer = INF;
        savedx = x;
        savedy = y;
        if(x == y)
        {
            answer = 0;
        }
        else
        {
            while(care[x] != care[y])
            {
                if(adancime[tata_lantz[care[x]]] < adancime[tata_lantz[care[y]]])
                    swap(x,y);
                if(care[x] == 1)
                    swap(x,y);
                line = care[x];
                A = 1;
                B = pozitie_nod[x];
                Aint.Querry(1,lantz[line].size()-1,1);
                x = tata_lantz[care[x]];
            }
            A = pozitie_nod[x];
            B = pozitie_nod[y];
            line = care[x];
            if(A > B) swap(A,B);
            ++A; /// nu ne intereseaza costul de a ajunge in A ci doar de la A la B
            if( A <= B )
                Aint.Querry(1,lantz[line].size()-1,1);
        }
        x = savedx;
        y = savedy;
        ZZ = answer;
        _X = (x*a + y*b) % N + 1;
        _Y = (y*c + ZZ*d) % N + 1;
        if( i > M - P )
            printf("%d\n",answer);
        x = _X;
        y = _Y;
    }
}


int main()
{
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);


    read();
    heavy_path_decomposition(); /// yeyyy
    Aint.Make();
    solve();

    return 0;
}