Cod sursa(job #6177)

Utilizator flo_demonBunau Florin flo_demon Data 17 ianuarie 2007 22:40:00
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <stdio.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>

#define MAX 32007

using namespace std;

int n, m, p;
int nod1, val;
int A, B, C, D, X, Y, Z, N;
int aux_x, aux_y;
vector<vector<int> > lV;
bool caract[MAX];
int noduri[2*MAX];
vector<map<int, int> > ad;
int cost[2*MAX];
int k, mat[2*MAX][18];
int part_size;
int first_ap[MAX];

void convert();
void dfs(int nod, int niv);
int query(int st, int dr);
void rmq();

int main()
{
    //read
    FILE *fin = fopen("atac.in", "r");
    fscanf(fin, "%d%d%d", &n, &m, &p);
    lV.resize(n+5);
    ad.resize(n+5);
    for (int i = 2; i <= n; ++i)
    {
        fscanf(fin, "%d%d", &nod1, &val);
        lV[nod1].push_back(i);
        lV[i].push_back(nod1);
        ad[nod1][i] = val;
        ad[i][nod1] = val;
    }
    fscanf(fin, "%d%d%d%d%d%d", &X, &Y, &A, &B, &C, &D);
    
    //solve
    lV[0].push_back(1);
    lV[1].push_back(0);
    dfs(0, 0);     
    for (int i = 0; i < N-1; ++i)
        cost[i+1] = ad[noduri[i]][noduri[i+1]];
    rmq();
    
    //write
    FILE *fout = fopen("atac.out", "w");
    for (int i = 1; i <= m; ++i)
    {
        Z = cost[query(first_ap[X], first_ap[Y])]; 
        if ((i-p) >= 0)
            fprintf(fout, "%d\n", Z);
        convert();
    }
    fclose(fout);
    fclose(fin);
    
    return 0;
}

void convert()
{
    aux_x = (X * A + Y * B) % n + 1;
    aux_y = (Y * C + Z * D) % n + 1;
    X = aux_x;
    Y = aux_y;
}

void dfs(int nod, int niv)
{
    vector<int>::iterator start, end;
    start = lV[nod].begin();
    end = lV[nod].end();
    caract[nod] = true;
    noduri[N++] = nod;
    first_ap[nod] = N-1;
    for (; start != end; ++start)
        if (!caract[(*start)])
        {
            dfs((*start), niv+1);
            noduri[N++] = nod;
        }
}

void rmq()
{
    for (int i = 1; i <= N; ++i)
        mat[i][0] = i;
    for (int j = 1; j <= N; ++j)
    {
        part_size = (1 << j);
        if (part_size > N) break;
        for (int i = 1; (i + part_size) - 1 <= N; ++i)
            if (cost[ mat[i][j-1] ] < cost[ mat[i + part_size / 2][j-1] ])
                mat[i][j] = mat[i][j-1];
            else
                mat[i][j] = mat[i + part_size / 2][j-1];
    } 
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j <= N; ++j)
        {
            part_size = (1 << j);
            if (i + part_size-1 > N) break;
        }
}

int query(int st, int dr)
{
    if (st > dr) swap(st, dr);
    k = (int)floor(log2(dr-st+1));
    part_size = (1 << k);
    if (cost[ mat[st][k] ] < cost[ mat[dr - part_size + 1][k] ])
        return mat[st][k];
    else
        return mat[dr - part_size + 1][k];
}