Cod sursa(job #1658305)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 21 martie 2016 12:33:34
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#define INF ((1<<30)-1)
#define us unsigned short
#define NMAX 100005
using namespace std;

vector<int> E, H, FirstPosition, aux, lg;
vector<vector<us> > RMQ;
vector<vector<pair<us, int> > > DMIN, G;
vector<bool> used;
int N, M, P, x, y, z, A, B, C, D;

void read();
void Euler(int us, int us);
void preprocesare();
us LCA(us a, us b);
void Solve();
int minStreet(us node, us ancestor);
int main()
{
    read();
    Solve();
    return 0;
}
void Solve()
{
    Euler(1, 0);
    preprocesare();
    int ancestor;
    for(int i=1; i<=M; ++i) {
        ancestor = LCA(x, y);
        if( x == y )
            z = 0;
        else
            z = min(minStreet(x, ancestor), minStreet(y, ancestor));
        if(i > M - P)
            cout<<z<<'\n';
        x = (x * A + y * B)%N + 1;
        y = (y * C + z * D)%N + 1;
    }
}
int minStreet(us node, us ancestor)
{
    int length = H[node] - H[ancestor], ans = INF;
    for(int k=0; k<18; ++k)
        if(length & (1<<k)) {
            ans = min(ans, DMIN[node][k].second);
            ancestor = DMIN[node][k].first;
        }
    return ans;
}
us LCA(us a, us b)
{
    a = FirstPosition[a];
    b = FirstPosition[b];
    if(a > b)
        swap(a, b);
    us 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 preprocesare()
{
    lg.assign(2, 0);
    for(int i=2; i <= 2 * E.size() + 10; ++i)
        lg.push_back(lg[i>>1] + 1);
    int maxLog = lg[E.size()-1];
    RMQ.assign(2 * E.size(), vector<us>(maxLog+2));
    for(int i=0; i<E.size(); ++i)
        RMQ[i][0] = E[i];
    for(int k=1; k<=maxLog; ++k) {
        for(int i=0; i<= E.size() - (1<<k) + 1; ++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(int i=1; i<=N; ++i) {
            DMIN[i][k].first = DMIN[ DMIN[i][k-1].first ][k-1].first;
            DMIN[i][k].second = min(DMIN[i][k-1].second, DMIN[ DMIN[i][k-1].first ][k-1].second);
        }
    }
}
void Euler(us node, us h)
{
    E.push_back(node);
    H[node] = h;
    FirstPosition[node] = E.size()-1;
    used[node] = true;
    for(us i=0; i<G[node].size(); ++i)
        if(used[G[node][i].first] == false) {
            Euler(G[node][i].first, h+1);
            E.push_back(node);
            DMIN[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);

    used.assign(N+2, false);
    H.assign(N+2, 0);
    FirstPosition.assign(N+2, 0);
    G.assign(N+2, vector<pair<us, int> >());
    DMIN.assign(N+2, vector<pair<us, int> >(18));

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