Cod sursa(job #377263)

Utilizator vladiiIonescu Vlad vladii Data 23 decembrie 2009 20:34:43
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.31 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

vector<int> G[32001];
struct Nr {
    int nod, lung;
} stra[18][32001];

int n, m, p;
bool viz[32001];
int H[64002], poz[64002], k, rmq[15][64002], L[64002], lg[64002];

void DFS(int nod, int lev) {
    //parcurgere Euler
    //nodurile sunt stocate in H[ ] si prima pozitia pe care apar ele in poz[ ]
    if(viz[nod]) { return; }
    viz[nod]=1;
    H[++k]=nod;
    L[k]=lev;
    poz[nod]=k;
    for(int i=0; i<G[nod].size(); i++) {
         DFS(G[nod][i], lev+1);
         H[++k]=nod;
         L[k]=lev;
    }
}

int min(int a, int b) {
    if(a<b) { return a; }
    return b;
}

int main() {
    fstream f1, f2;
    int i, j, x, y, z, a, b, c, d, aux, p, q, sol, t, st, minim;
    f1.open("atac.in", ios::in);
    f1>>n>>m>>p;
    for(i=2; i<=n; i++) {
         f1>>x>>y;
         G[x].push_back(i);
         //G[i].push_back(x);
         stra[0][i].nod=x;
         stra[0][i].lung=y;
    }
    f1>>x>>y>>a>>b>>c>>d;
    f1.close();
    for(i=1; i<=17; i++) {
         for(j=1; j<=n; j++) {
              stra[i][j].nod=stra[i-1][stra[i-1][j].nod].nod;
              stra[i][j].lung=min(stra[i-1][j].lung, stra[i-1][stra[i-1][j].nod].lung);
         }
    }
    DFS(1, 0);
    lg[1]=0;
    for(i=2; i<=k; i++) {
         lg[i]=lg[i >> 1] + 1;
    }
    for(i=1; i<=k; i++) {
         rmq[0][i]=i;
    }
    for(i=1; (1<<i)<k; ++i) {
         for(j=1; j<=k-(1 << i); ++j) {
              int l = 1 << (i - 1);
              rmq[i][j]=rmq[i-1][j];
              if(L[rmq[i-1][j+l]]<L[rmq[i][j]]) {
                   rmq[i][j] = rmq[i-1][j+l];
              }
         }
    }
    /**
    for(i=1; i<=n; i++) { cout<<L[poz[i]]<<endl; }
    **/
    for(i=1; i<=m-p; i++) {
         //aflu min dintre x si y
         st=poz[x]; q=poz[y];
         if(st>q) { swap(st, q); }
         //(int)(floor(log2((double)(n))));
         t=lg[q-st+1];
         aux=q-st+1-(1 << t);
         //rmq[x][p], rmq[x][p+aux]
         sol=rmq[t][st];
         if(L[sol]>L[rmq[t][st+aux]]) {
              sol=rmq[t][st+aux];
         }
         //cout<<"X: "<<x<<" ,Y: "<<y<<", niv="<<L[sol]<<endl;
         st=L[poz[x]]; q=L[poz[y]];
         //aflu minimul de la x la H[sol] = LCA (x, y)
         t=st-L[sol];
         aux=x; j=0;
         minim=999999999;
         while(t) {
              if(t%2) {
                   minim=min(minim, stra[j][aux].lung);
                   aux=stra[j][aux].nod;
              }
              j++; t=t>>1;
         }
         //minim=min(minim, stra[j-1][aux].lung);
         t=q-L[sol];
         aux=y; j=0;
         while(t) {
              if(t%2) {
                   minim=min(minim, stra[j][aux].lung);
                   aux=stra[j][aux].nod;
              }
              j++; t=t>>1;
         }
         //minim=min(minim, stra[j-1][aux].lung);
         z=minim;
         x=(x*a+y*b)%n+1;
         y=(y*c+z*d)%n+1;
    }
    f2.open("atac.out", ios::out);
    for(i=1; i<=p; i++) {
         //aflu min dintre x si y
         st=poz[x]; q=poz[y];
         if(st>q) { swap(st, q); }
         //(int)(floor(log2((double)(n))));
         t=lg[q-st+1];
         aux=q-st+1-(1 << t);
         //rmq[x][p], rmq[x][p+aux]
         sol=rmq[t][st];
         if(L[sol]>L[rmq[t][st+aux]]) {
              sol=rmq[t][st+aux];
         }
         //cout<<"X: "<<x<<" ,Y: "<<y<<", niv="<<L[sol]<<endl;
         st=L[poz[x]]; q=L[poz[y]];
         //aflu minimul de la x la H[sol] = LCA (x, y)
         t=st-L[sol];
         aux=x; j=0;
         minim=999999999;
         while(t) {
              if(t%2) {
                   minim=min(minim, stra[j][aux].lung);
                   aux=stra[j][aux].nod;
              }
              j++; t=t>>1;
         }
         //minim=min(minim, stra[j-1][aux].lung);
         t=q-L[sol];
         aux=y; j=0;
         while(t) {
              if(t%2) {
                   minim=min(minim, stra[j][aux].lung);
                   aux=stra[j][aux].nod;
              }
              j++; t=t>>1;
         }
         //minim=min(minim, stra[j-1][aux].lung);
         z=minim;
         f2<<z<<endl;
         x=(x*a+y*b)%n+1;
         y=(y*c+z*d)%n+1; 
    }        
    f2.close();
    return 0;
}