Cod sursa(job #2642197)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 13 august 2020 23:03:10
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define nod first
#define cst second
using namespace std;
const int NMAX = 32000;
const int INF = 2.e9;
typedef pair <int , int> muchii;
vector <muchii> G[NMAX + 5];
int lvl[2 * NMAX + 5] , t[2 * NMAX + 5] , h[NMAX + 5] , ord;
int d[2 * NMAX + 5][18] , log2[2 * NMAX + 5];
int anc[NMAX + 5][18] , c[NMAX + 5][18]; //anc[i][j]=al 2^j stramos al nodului i , c[i][j] = costul minim de la nodul i pana la al 2^j stramos;
int st[NMAX + 5];
int n;
void rmq()
{
    int i , j;
    for(i = 1 ; i <= ord ; i ++)
        d[i][0] = i;
    for(j = 1 ; (1 << j) <= ord ; j ++)
        for(i = 1 ; i + (1 << j) - 1 <= ord ; i ++)
            if(lvl[d[i][j - 1]] <= lvl[d[i + (1 << (j - 1))][j - 1]])
                d[i][j] = d[i][j - 1];
            else
                d[i][j] = d[i + (1 << (j - 1))][j - 1];
}
int query(int x , int y)
{
    int p = log2[y - x + 1];
    if(lvl[d[x][p]] <= lvl[d[y - (1 << p) + 1][p]])
        return t[d[x][p]];
    return t[d[y - (1 << p) + 1][p]];
}
void dfs(int u , int l)
{
    int v , j , k;
    h[u] = ++ ord;
    t[ord] = u;
    lvl[ord] = l;
    st[l] = u;
    for(j = 0 ; j < G[u].size() ; j ++)
    {
        v = G[u][j].nod;
        if(!h[v])
        {
            for(k = 0 ; (1 << k) <= l ; k ++)
            {
                anc[v][k] = st[l - (1 << k) + 1];
                if(k == 0)
                    c[v][k] = G[u][j].cst;
                else
                    c[v][k] = min(c[v][k - 1] , c[anc[v][k - 1]][k - 1]);
            }
            dfs(v , l + 1);
            t[++ ord] = u;
            lvl[ord] = l;
        }
    }
}
int get_min(int x , int y)
{
    int dif , minim , i , p;
    minim = INF;
    dif = lvl[h[x]] - lvl[h[y]];
    i = 0;
    for(p = dif ; p > 0 ; p = (p >> 1))
    {
        if(p & 1)
        {
            minim = min(minim , c[x][i]);
            x = anc[x][i];
        }
        i ++;
    }
    return minim;
}
int main()
{
    freopen("atac.in" , "r" , stdin);
    freopen("atac.out" , "w" , stdout);
    int m , p , i , j , x , y , xc , yc , A , B , C , D , z;
    scanf("%d%d%d" , &n , &m , &p);
    for(i = 1 ; i < n ; i ++)
    {
        scanf("%d%d" , &x , &y);
        G[x].push_back({i + 1 , y});
        G[i + 1].push_back({x , y});
    }
    scanf("%d%d%d%d%d%d" , &xc , &yc , &A , &B , &C , &D);
    dfs(1 , 1);
    rmq();
    for(i = 2 ; i <= ord ; i = (i << 1))
        log2[i] = 1;
    for(i = 1 ; i <= ord ; i ++)
        log2[i] += log2[i - 1];
    for(i = 1 ; i <= m ; i ++)
    {
        if(xc == yc)
            z = 0;
        else
        {
            x = min(h[xc] , h[yc]);
            y = max(h[xc] , h[yc]);
            int lca = query(x , y);
            z = min(get_min(xc , lca) , get_min(yc , lca));
        }
        xc = (xc * A + yc * B) % n + 1;
        yc = (yc * C + z * D) % n + 1;
        if(i > m - p)
            printf("%d\n" , z);
    }
    return 0;
}