Mai intai trebuie sa te autentifici.

Cod sursa(job #1386768)

Utilizator taigi100Cazacu Robert taigi100 Data 13 martie 2015 11:15:26
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.91 kb
/*
     Keep It Simple!
*/

#include <fstream>
#include <vector>

using namespace std;

const int kMaxN = 32005;
const int kMaxLb = 17;
const int kInf = 0x3f3f3f3f;

typedef pair<int,int> pii;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

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

int N,M,P;
vector<pii> G[kMaxN];
long long X,Y,A,B,C,D;
int lb[kMaxN << 1],lvl[kMaxN],first[kMaxN];
int rmq[kMaxLb][kMaxN << 1];
pii dp[kMaxLb][kMaxN];
int euler_sz;
bool used[kMaxN];


void ReadInput()
{
     int x,y;
     fin >> N >> M >> P;
     for(int i=2; i<=N; ++i)
     {
          fin >> x >> y;
          G[i].pb(mp(x,y));
          G[x].pb(mp(i,y));
     }
     fin >> X >> Y >> A >> B >> C >> D;
}

void ComputeLb()
{
     for(int i=2; i< (kMaxN<<1); ++i)
          lb[i] = lb[i>>1]+1;
}

void DFS(int node,int lv)
{
     rmq[0][++euler_sz] = node;
     first[node] = euler_sz;
     used[node] = true;

     for(auto it:G[node])
          if(!used[it.fi])
          {
               dp[0][it.fi] = mp(node,it.se);
               lvl[it.fi] = lv+1;
               DFS(it.fi,lv+1);
               rmq[0][++euler_sz] = node;
          }
}

int MinLvl(int a,int b)
{
     if(lvl[a] < lvl[b])
          return a;
     return b;
}

void ComputeDynamics()
{
     for(int i=1; i<kMaxLb; ++i)
          for(int j=1; j<=N; ++j)
               dp[i][j].fi = -1;

     for(int i=1; i<kMaxLb; ++i)
     {
          for(int j=1; j<=N; ++j)
               if(dp[i-1][j].fi != -1)
               {
                    dp[i][j].fi = dp[i-1][dp[i-1][j].fi].fi;
                    dp[i][j].se = min(dp[i-1][j].se,dp[i-1][dp[i-1][j].fi].se);
               }
          for(int j=1; j + (1<<i) <= euler_sz; ++j)
               rmq[i][j] = MinLvl(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
     }
}

void ComputeData()
{
     lvl[1] = 1;
     DFS(1,1);
     ComputeLb();
     ComputeDynamics();
}

int FindLca(int x,int y)
{
     int a = first[x],b=first[y];
     if(a > b) swap(a,b);

     int len = lb[b-a];

     return MinLvl(rmq[len][a],rmq[len][b-(1<<len)+1]);
}

int MinEdge(int x,int y)
{
     int ans = kInf;
     int diff = lvl[x]-lvl[y];
     for(int i=0; i<kMaxLb; ++i)
          if(diff & (1<<i))
          {
               ans = min(ans,dp[i][x].se);
               x = dp[i][x].fi;
          }
     return ans;
}

int Query(int x,int y)
{
     if(x == y) return 0;

     int lca = FindLca(x,y);

     return min(MinEdge(x,lca),MinEdge(y,lca));
}

void PrintQueries()
{
     long long ans;
     while(M--)
     {
          ans = Query(X,Y);
          if(P > M)
               fout << ans << '\n';
          X = (X*A + Y*B)%N + 1;
          Y = (Y*C + ans*D)%N + 1;
     }
}

void Solve()
{
     ReadInput();
     ComputeData();
     PrintQueries();
}

int main()
{
     Solve();
     return 0;
}