Cod sursa(job #2636922)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 20 iulie 2020 17:19:35
Problema Atac Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 1000;
const int INF = 2.e9;
vector <int> 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] , cst[NMAX + 5][NMAX + 5];
int n , root;
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;
    h[u] = ++ ord;
    t[ord] = u;
    lvl[ord] = l;
    for(j = 0 ; j < G[u].size() ; j ++)
    {
        v = G[u][j];
        if(!h[v])
        {
            dfs(v , l + 1);
            t[++ ord] = u;
            lvl[ord] = l;
        }
    }
}
int get_z(int x , int y , int lca)
{
    int l , minim , i;
    minim = INF;
    i = x;
    l = lvl[x];
    do
    {
        i ++;
        if(lvl[i] == l - 1)
        {
            minim = min(cst[t[x]][t[i]] , minim);
            l --;
            x = i;
        }
    }
    while(t[i] != lca);
    i = y;
    l = lvl[y];
    do
    {
        i --;
        if(lvl[i] == l - 1)
        {
            minim = min(cst[t[y]][t[i]] , minim);
            l --;
            y = i;
        }
    }
    while(t[i] != lca);
    return minim;
}
int main()
{
    freopen("atac.in" , "r" , stdin);
    freopen("atac.out" , "w" , stdout);
    int m , p , i , 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);
        G[i + 1].push_back(x);
        cst[x][i + 1] = cst[i + 1][x] = y;
    }
    scanf("%d%d%d%d%d%d" , &xc , &yc , &A , &B , &C , &D);
    root = 1;
    dfs(root , 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 = get_z(x , y , 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;
}