Cod sursa(job #1148192)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 20 martie 2014 16:10:31
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define NMAX 32007
#define LMAX 17
#define MAX 2000000000

using namespace std;

vector< pair< int, int > > v[NMAX];
int D[LMAX][NMAX], Level[NMAX], Mat[LMAX][NMAX];
int n, m, p;

void Dfs_Level(int Nod, int dad, int Cost) {
    D[0][Nod] = dad;
    Level[Nod] = Level[dad] + 1;
    Mat[0][Nod] = Cost;
    for(vector< pair< int, int > >::iterator it = v[Nod].begin(); it != v[Nod].end(); ++ it)
        if(it->first != dad)
            Dfs_Level(it->first, Nod, it->second);
}

void Dinamica_stramosi(){
    for(int i = 1; (1 << i) <= n; ++i)
        for(int j = 1; j <= n; ++j){
            D[i][j] = D[i - 1][D[i - 1][j]];
            Mat[i][j] = min(Mat[i - 1][j], Mat[i - 1][D[i - 1][j]]);
        }
}

inline int LCA(int a, int b){
    int Min = MAX;
    if(Level[a] < Level[b])
        swap(a, b);
    for(int i = LMAX - 1; i >= 0; --i)
        if(Level[D[i][a]] >= Level[b]){
            Min = min(Min, Mat[i][a]);
            a = D[i][a];
        }
    if(a == b)
        return Min;
    for(int i = LMAX - 1; i >= 0; --i)
        if(D[i][a] != D[i][b]){
            Min = min(Min, Mat[i][a]);
            Min = min(Min, Mat[i][b]);
            a = D[i][a];
            b = D[i][b];
        }
    Min = min(Min, Mat[0][a]);
    Min = min(Min, Mat[0][b]);
    return Min;
}

int main(){
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
    scanf("%d %d %d", &n, &m, &p);
    for(int i = 2; i <= n; ++i){
        int a = 0, Cost = 0;
        scanf("%d %d", &a, &Cost);
        v[a].push_back(make_pair(i, Cost));
        v[i].push_back(make_pair(a, Cost));
    }
    Dfs_Level(1, 0, MAX);
    Dinamica_stramosi();
    /**for(int i = 1; i <= n; ++i, printf("\n"))
        for(int j = 1; j <= n; ++j)
            printf("%d ", D[i][j]);
    printf("\n");
    for(int i = 1; i <= n; ++i, printf("\n"))
        for(int j = 1; j <= n; ++j)
            printf("%d ", Mat[i][j]);**/
    int x, y, a, b, c, d;
    scanf("%d %d %d %d %d %d", &x, &y, &a, &b, &c, &d);
    for(int i = 1; i <= m; ++i){
        int Ans = LCA(x, y);
        if(Ans == 2000000000)
            Ans = 0;
        if(i >= m - p + 1)
            printf("%d\n", Ans);
        x = (x * a + y * b) % n + 1;
        y = (y * c + Ans * d) % n + 1;
    }
    return 0;
}