Cod sursa(job #2488752)

Utilizator StanCatalinStanCatalin StanCatalin Data 7 noiembrie 2019 16:32:44
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("atac.in");
ofstream out("atac.out");

const int dim = 32005;

int n,m,p,x,y,a,b,c,d,z,intra[dim],lv[dim],l[4*dim],cnt,lg[4*dim],rmq[32][4*dim],rmq_2[32][dim],str[32][dim];
vector <pair <int,int> > vec[dim];

int new_x(int x,int y)
{
   return ((x*a + y*b)%(n) + 1);
}

int new_y(int y, int rasp)
{
   return ((y*c + rasp*d)%(n) + 1);
}

void DFS(int nod,int level,int parent)
{
    lv[nod] = level;
    l[++cnt] = nod;
    intra[nod] = cnt;

    int maxi = vec[nod].size();
    for (int i=0; i<maxi; i++)
    {
        int v = vec[nod][i].first;
        if (v != parent)
        {
           DFS(v , level+1, nod);
           l[++cnt] = nod;
        }
    }
}

void DFS_2(int nod,int parent)
{
     for (auto v : vec[nod])
     {
        if (v.first != parent)
        {
           rmq_2[0][v.first] =  rmq_2[1][v.first] = v.second;
           str[1][v.first] = nod;
           DFS_2(v.first,nod);
        }
     }
}

int lca(int x,int y)
{
    x = intra[x];
    y = intra[y];
    if (x > y) swap(x,y);

    int dif = lg[y - x + 1];

    if(lv[rmq[dif][x]] <= lv[rmq[dif][y+1 - (1<<dif)]])
    {
        return rmq[dif][x];
    }
    return rmq[dif][y+1 - (1<<dif)];
}

int mini(int x,int y)
{
     int rasp = 1000000;

     while (y != x)
     {
         int dif = lv[y] - lv[x];
         dif = lg[dif];

         rasp = min(rasp , rmq_2[dif][y]);
         y = str[1][str[dif][y]];
     }
     return rasp
     ;
}

int main()
{
    in >> n >> m >> p;

    for (int i=2,v,cost; i<=n; i++)
    {
       in >> v >> cost;
       vec[i].push_back({v,cost});
       vec[v].push_back({i,cost});
    }

    in >> x >> y >> a >> b >> c >> d;

    DFS(1,1,0);
    for (int i=2; i<=cnt; i++)
    {
        lg[i] = lg[i/2] + 1;
    }


    for (int i=1; i<=cnt; i++)
    {
       rmq[0][i] = l[i];
    }

    for (int k=1; (1<<k) <= cnt; k++)
    {
       for (int j=1; j+(1<<k)-1<=cnt; j++)
       {
            if (lv[rmq[k-1][j]] <= lv[rmq[k-1][j + (1<<(k-1))]])
            {
                rmq[k][j] = rmq[k-1][j];
            }
            else
            {
               rmq[k][j] = rmq[k-1][j + (1<<(k-1))];
            }
       }
    }

    for (int i=1; i<=n; i++) str[0][i] = i;
    DFS_2(1,0);

    for (int i=1; (1<<i)<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
           str[i][j] = str[1][str[i-1][str[i-1][j]]];
        }
    }

    for (int i=0; i<=20; i++)
    {
        rmq_2[i][1] = n;
    }

    for (int i=1; (1<<i) <= n; i++)
    {
       for (int j=1; lv[j] + (1<<i)<=n ; j++)
       {
          rmq_2[i][j] = min(rmq_2[i-1][j] , rmq_2[i-1][ str[1][str[i-1][j]] ]);
       }
    }

    for (int i=1; i<=m; i++)
    {
       int lc = lca(x,y);

       int rasp;

       if (x == y) rasp = 0;
       else if (lc == x) rasp = mini(lc,y);
       else if (lc == y) rasp = mini(lc,x);
       else rasp = min( mini(lc,x) , mini(lc,y));
       x = new_x(x,y);
       y = new_y(y,rasp);

       if (i >= m-p + 1)
       {
          out << rasp << "\n";
       }
    }
    return 0;
}