Cod sursa(job #2570982)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 4 martie 2020 20:20:44
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.5 kb
#include <bits/stdc++.h>
#define FILE_NAME "atac"
#define fast ios_base :: sync_with_stdio(0); cin.tie(0);
#pragma GCC optimize("O3")
#define NMAX 32000 + 100
using namespace std;

ifstream f(FILE_NAME ".in");
ofstream g(FILE_NAME ".out");

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> llp;
typedef pair<ld,ld> pct;

const ll inf = 1LL << 60;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;


void add(ll &a , ll b)
{
    a += b;
    a %= mod;
}

void sub(ll &a, ll b)
{
    a = (a - b + mod) % mod;
}

int n, m, p, ne, x, y,A, B, C, D ,X1, Y1;
vector <pi> G[NMAX];
int pd[18][2 *NMAX], lvl[NMAX], euler[2*NMAX], str[18][NMAX], cost[18][NMAX],
    niv[2*NMAX], ln[2*NMAX], lst[NMAX];

void DFS(int nod)
{
    euler[++ne] = nod;
    niv[ne] = lvl[nod];
    for(auto it : G[nod])
    {
        int urm = it.first;
        lvl[urm] = lvl[nod] + 1;
        str[0][it.first] = nod;
        cost[0][it.first] = it.second;
        DFS(urm);

        euler[++ne] = nod;
        niv[ne] = lvl[nod];
    }
    lst[nod] = ne;
}
void RMQ()
{
    for(int i = 2; i <= ne; ++i)
        ln[i] = 1 + ln[i >> 1];
    for(int i = 1; i <= ne; ++i)
        pd[0][i] = i;
    for(int i = 1; i <= ln[ne]; ++i)
    {
        int k = 1 << (i - 1);
        for(int j = 1; j <= ne; ++j) ///pd[i][j] = min(pd[i-1][j], pd[i-1][j + k])
            if(niv[ pd[i - 1][j] ] < niv[ pd[i - 1][j + k] ])
                pd[i][j] = pd[i - 1][j];
            else
                pd[i][j] = pd[i - 1][j + k];
    }
}
int LCA(int x, int y)
{
    int a = min(lst[x], lst[y]);
    int b = max(lst[x], lst[y]);
    int d = ln[b - a + 1];
    int ans = pd[d][a];
    if(niv[ ans ] > niv[ pd[d][b - (1 << d) + 1] ])
        ans = pd[d][b - (1 << d) + 1];
    return euler[ans];
}
void precalc()
{
    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] ];
            cost[i][j] = min(cost[i - 1][j], cost[i - 1][ str[i - 1][j] ]);
        }
}
int main()
{
    f >> n >> m >> p;
    for(int i = 2; i <= n; ++i)
    {
        f >> x >> y;
        G[x].push_back({i,y});
    }
    DFS(1);
    RMQ();
    precalc();
    f >> X1 >> Y1 >> A >> B >> C >> D;
    for(int i = 1; i <= m; ++i)
    {
        int mini = 1 << 30;
        if(X1 != Y1)
        {
            int stramos = LCA(X1, Y1);
            int cx = X1;
            int cy = Y1;
            int difx = lvl[cx] - lvl[stramos];
            int dify = lvl[cy] - lvl[stramos];
            int up = 0;

            while(difx > 0 && X1 > 0)
            {
                if(difx & 1)
                {
                    mini = min(mini, cost[up][X1]);
                    X1 = str[up][X1];
                }
                up++;
                difx >>= 1;
            }
            up = 0;

            while(dify > 0 && Y1 > 0)
            {
                if(dify & 1)
                {
                    mini = min(mini, cost[up][Y1]);
                    Y1 = str[up][Y1];
                }
                up++;
                dify >>= 1;
            }
            if(mini == 1 << 30)
                mini = 0;
            X1 = cx;
            Y1 = cy;
        }
        else
            mini = 0;
        if(m - i < p)
            g << mini << '\n';

        X1 = (X1 * A + Y1 * B) % n + 1;
        Y1 = (Y1 * C + mini * D) % n + 1;
    }
    f.close();
    g.close();
    return 0;
}