Cod sursa(job #6318)

Utilizator flo_demonBunau Florin flo_demon Data 18 ianuarie 2007 20:23:18
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <stdio.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>

#define MAX 32007
#define INF 99999999

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 k, mat[2*MAX][18], nivel[2*MAX];
int part_size;
int first_ap[MAX];
int t[MAX], lca, best;

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);     
    rmq();
    
    FILE *fout = fopen("atac.out", "w");
  /*  for (int i = 1; i <= m; ++i)
    {
        lca = noduri[query(first_ap[X], first_ap[Y])];
        aux_x = X;
        aux_y = Y;
        best = INF;
        while (t[aux_x] != lca)
        {
            if (ad[aux_x][t[aux_x]] < best)
                best = ad[aux_x][t[aux_x]];
            aux_x = t[aux_x];            
        }
        if (ad[aux_x][t[aux_x]] < best)
            best = ad[aux_x][t[aux_x]];
            
        while (t[aux_y] != lca)
        {
            if (ad[aux_y][t[aux_y]] < best)
                best = ad[aux_y][t[aux_y]];
            aux_y = t[aux_y];            
        }
        if (ad[aux_y][t[aux_y]] < best)
            best = ad[aux_y][t[aux_y]];
        Z = best;
        if ((i-p) >= 0)
            fprintf(fout, "%d\n", Z);
       // cout << X << " " << Y << " " << Z << "\n";
        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;
    nivel[N-1] = niv;
    first_ap[nod] = N-1;
    for (; start != end; ++start)
        if (!caract[(*start)])
        {
            dfs((*start), niv+1);
            t[(*start)] = nod;
            noduri[N++] = nod;
            nivel[N-1] = niv;
        }
}

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 (nivel[ mat[i][j-1] ] < nivel[ 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];
    } 
}

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