Cod sursa(job #1658491)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 21 martie 2016 16:20:27
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
//#define usi unsigned short int
#define INF ((1<<30)-1)
using namespace std;
typedef unsigned short int usi;

vector<usi> E, H, FirstPosition, lg;
vector<vector<usi> > RMQ;
vector<vector<pair<usi, int> > > G, minS;
int N, M, P, x, y, z, A, B, C, D;
const int lgMax = 18;

void read();
void Solve();
void Euler(usi node, usi h);
void prepare();
int minStreet(usi node, usi anc);
usi LCA(usi a, usi b);

int main()
{
    read();
    Solve();
    return 0;
}
void Solve()
{
    Euler(1, 0);
    prepare();
    for(int i=1; i<=M; ++i) {
        usi anc = LCA(x, y);
        if( x == y )                z = 0;
        else if( x == anc)          z = minStreet(y, x);
        else if(y == anc)           z = minStreet(x, y);
        else                        z = min(minStreet(x, anc), minStreet(y, anc));
        if(i > M - P)
            cout<<z<<'\n';
        x = (x * A + y * B)%N + 1;
        y = (y * C + z * D)%N + 1;
    }
}
int minStreet(usi node, usi anc)
{
    usi length = H[node] - H[anc];
    int ans = INF;
    for(usi k=0; k<=lg[length]; ++k)
        if(length & (1<<k)) {
            ans = min(ans, minS[node][k].second);
            node = minS[node][k].first;
        }
    return ans;
}
usi LCA(usi a, usi b)
{
    a = FirstPosition[a];
    b = FirstPosition[b];
    if(a > b)   swap(a, b);
    usi k = lg[b-a+1];
    if(H[RMQ[a][k]] < H[RMQ[b-(1<<k)+1][k]])
        return RMQ[a][k];
    else
        return RMQ[b-(1<<k)+1][k];
}
void prepare()
{
    lg.assign(2, 0);
    int lengthE = E.size();
    for(int i=2; i <= 2 * lengthE + 10; ++i)
        lg.push_back(lg[i>>1] + 1);

    usi maxLog = lg[lengthE-1];
    RMQ.assign(2 * lengthE, vector<usi>(lgMax));
    for(int i=0; i<lengthE; ++i)
        RMQ[i][0] = E[i];

    for(usi k=1; k<=maxLog; ++k) {
        for(int i=0; i<= lengthE; ++i)
            if(H[RMQ[i][k-1]] < H[RMQ[i+(1<<(k-1))][k-1]])
                RMQ[i][k] = RMQ[i][k-1];
            else
                RMQ[i][k] = RMQ[i+(1<<(k-1))][k-1];

        for(usi i=1; i<=N; ++i) {
            minS[i][k].first = minS[ minS[i][k-1].first ][k-1].first;
            minS[i][k].second = min(minS[i][k-1].second, minS[ minS[i][k-1].first ][k-1].second);
        }
    }
}
void Euler(usi node, usi h)
{
    E.push_back(node);
    H[node] = h;
    FirstPosition[node] = E.size()-1;
    for(usi i=0; i<G[node].size(); ++i) {
        Euler(G[node][i].first, h+1);
        E.push_back(node);
        minS[G[node][i].first][0] = make_pair(node, G[node][i].second);
    }
}
void read()
{
    freopen("atac.in", "rt", stdin);
    freopen("atac.out", "wt", stdout);
    scanf("%d%d%d", &N, &M, &P);

    H.assign(N+2, 0);
    FirstPosition.assign(N+2, 0);
    G.assign(N+2, vector<pair<usi, int> >());
    minS.assign(N+2, vector<pair<usi, int> >(lgMax));

    usi a;  int v;
    for(usi i=2; i<=N; ++i) {
        scanf("%d%d", &a, &v);
        G[a].push_back(make_pair(i, v));
    }
    scanf("%d%d%d%d%d%d", &x, &y, &A, &B, &C, &D);
}