Cod sursa(job #2488251)

Utilizator StanCatalinStanCatalin StanCatalin Data 6 noiembrie 2019 16:13:50
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 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] = v.second;
           str[0][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 dif = lv[y] - lv[x] + 1;

     dif = lg[dif];

     if (lv[y] == lv[x] + 1)
     {
        return rmq_2[0][y];
     }

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


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))];
            }
       }
    }

    DFS_2(1,0);

    for (int i=1; (1<<i)<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
           str[i][j] = 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[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;
}