Cod sursa(job #3217177)

Utilizator NathanBBerintan Emanuel Natanael NathanB Data 21 martie 2024 16:40:39
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 6.03 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct custom_hash_pair {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(pair<uint64_t,uint64_t> x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
    }
};

#define all(x) (x).begin(), (x).end()
#define allg(x) (x).begin(), (x).end(), greater<int>()
using ull = unsigned long long;
using ll =  long long;
using ld = double;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<ld>;
using si = set<int>;
using ssi = set<si>;
using sl = set<ll>;
using ssl = set<sl>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvl = vector<vl>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vs = vector<string>;
using vpi = vector<pii>;
using vpl = vector<pll>;
using vvpl = vector<vpl>;
#define umap unordered_map
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define ff first
#define ss second
#define ar array
inline void yn(bool b)
{
    if(b==true)
        cout<<"Yes\n";
    else
        cout<<"No\n";
}
  inline void fastio() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

ll Mod = 1e9+7;
inline bool hasbit(ll nr, ll pos)
{
    return (nr&(1ll<<pos));
}

const string TASK("atac");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout
const ll Inf = 0x3f3f3f3f;
bool testCase = false;
const ll Nmax=2e5+10;
const ll LOG=18;
ll n,m,first[Nmax],cnt=0,p[Nmax],h[Nmax],rmq[LOG][Nmax],pct[Nmax],in[Nmax],dp[LOG][Nmax],tata[LOG][Nmax],hin[Nmax];
ll X,Y,A,B,C,D,P;
vl ans;
vl G[Nmax];
void dfs(int nod,int hi)
{
  cnt++;
  h[cnt] = hi;
  hin[nod] = hi;
  p[cnt] = nod;
  if(first[nod]==0)
    first[nod] = cnt;
  for(auto c:G[nod])
    {dfs(c,hi+1);
    cnt++;
    p[cnt] = nod;
    h[cnt] = hi;}
}

void solve_testcase()
{
  cin>>n>>m>>P;
  for(int i=2;i<=n;i++)
  {
    ll x,y;
    cin>>x>>y;
    G[x].eb(i);
    tata[0][i] = x;
    dp[0][i] = y;
    in[i]++;
    pct[i] = y;
  }
  for(int i=1;i<=n;i++)
    if(in[i]==0)
  {
    dfs(i,0);
    break;
  }
  for(int i=1;i<=cnt;i++)
    rmq[0][i] = i;
  for(int l=1;l<LOG;l++)
  {
    for(int i=1;i+(1<<l)<=cnt;i++)
    {
      ll p1 = rmq[l-1][i];
      ll p2 = rmq[l-1][i+(1<<(l-1))];
      if(h[p1]<=h[p2])
        rmq[l][i] = p1;
      else rmq[l][i] = p2;
    }
  }
  for(int i=0;i<LOG;i++)
  {
    tata[i][1] = 0;
    dp[i][1] = Inf;
  }
  for(int l=1;l<LOG;l++)
  {
    for(int i=2;i<=n;i++)
    {
      tata[l][i] = tata[l-1][tata[l-1][i]];
      dp[l][i] = min(dp[l-1][i],dp[l-1][tata[l-1][i]]);
    }
  }
  /*for(int i=1;i<=cnt;i++)
    cout<<p[i]<<" ";
  cout<<'\n';
  for(int i=1;i<=cnt;i++)
    cout<<h[i]<<" ";
  cout<<'\n';*/
  cin>>X>>Y>>A>>B>>C>>D;
  ll xnow = X;
  ll ynow = Y;
  for(int i=1;i<=m;i++)
  {
    ll lst = 0, pnow = xnow;
    if(xnow==ynow)
    {
      ans.eb(0);
      xnow = (xnow * A + ynow * B) % n + 1;
      ynow = (ynow * C + 0 * D) % n + 1;
      /// Change here, need to go to next position
      continue;
    }
    ll fxnow = first[xnow];
    ll fynow = first[ynow];
    //cout<<rmq[1][fxnow]<<'\n';
    if(fxnow > fynow)swap(fxnow,fynow);
    ll lca;
    ll lma = 0;
    while(fxnow+(1<<(lma+1))<=fynow)
    lma++;
    ll a11 = rmq[lma][fxnow];
    ll a22 = rmq[lma][fynow-(1<<lma)+1];
    if(h[a11] <= h[a22])
      lca = p[a11];
    else lca = p[a22];
    //cout<<xnow<<" "<<ynow<<" "<<"lca = "<<lca<<'\n';
    ll wewant = hin[lca];
    ll wexnow = hin[xnow],weynow = hin[ynow];
    ll mist = Inf, midr = Inf;
    ll auxx = xnow;
    ll auxy = ynow;
    while(wexnow!=wewant)
    {
      ll l=0;
      while(wexnow-(1<<(l+1)) >= wewant)
        l++;
      mist = min(mist,dp[l][auxx]);
      auxx = tata[l][auxx];
      wexnow = hin[auxx];
    }
    while(weynow!=wewant)
    {
      ll l=0;
      while(weynow-(1<<(l+1)) >= wewant)
        l++;
      midr = min(midr,dp[l][auxy]);
      auxy = tata[l][auxy];
      weynow = hin[auxy];
    }
    ll dist = min(midr,mist);
    //cout<<xnow<<" "<<ynow<<" "<<dist<<'\n';
    ans.eb(dist);
    xnow = (xnow * A + ynow * B) % n + 1;
    ynow = (ynow * C + dist * D) % n + 1;
  }
  vl afis;
  for(int i=1;i<=P;i++)
    afis.eb(ans[ans.size()-i]);
  reverse(all(afis));
  for(auto i:afis)
    cout<<i<<'\n';
  //cout<<dp[1][7]<<'\n';
  /*for(int i=1;i<=cnt;i++)
    cout<<p[i]<<" ";
  cout<<'\n';
  for(int i=1;i<=cnt;i++)
    cout<<h[i]<<" ";*/
}

void pregenerate()
{

}

/// Check for interruption of input!!
/// a+b=a^b+2*(a&b)
int main() {
    fastio();
    pregenerate();
    ll t=1;
    if (testCase) cin >> t;
    while (t--)
    {   //cout<<t<<endl;
        solve_testcase();
    }
    return 0;
}