Cod sursa(job #2637057)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 20 iulie 2020 23:53:21
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.54 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 32000;
const int INF = 2.e9;
struct muchii
{
    int nod , cost;
    muchii(int x = 0 , int y = 0)
    {
        nod = x;
        cost = y;
    }
};
vector <muchii> G[NMAX + 5];
int lvl[2 * NMAX + 5] , t[2 * NMAX + 5] , h[NMAX + 5] , ord , cnt;
int d[2 * NMAX + 5][17] , log2[2 * NMAX + 5] , dad[NMAX + 5] , c[NMAX + 5] , fr[NMAX + 5] , s[NMAX + 5];
int d2[NMAX + 5][17];
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 lvl[d[x][p]];
    return lvl[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].nod;
        if(!h[v])
        {
            dad[v] = u;
            c[v] = G[u][j].cost;
            dfs(v , l + 1);
            t[++ ord] = u;
            lvl[ord] = l;
        }
    }
}
int r[1505][1005][12];
void rmq2(int d1[][12])
{
    int i , j , lg;
    lg = s[0];
    for(i = 1 ; i <= lg ; i ++)
        d1[i][0] = s[i];
    for(j = 1 ; (1 << j) <= lg ; j ++)
        for(i = 1 ; i + (1 << j) - 1 <= lg ; i ++)
            if(d1[i][j - 1] <= d1[i + (1 << (j - 1))][j - 1])
                d1[i][j] = d1[i][j - 1];
            else
                d1[i][j] = d1[i + (1 << (j - 1))][j - 1];
}
int query2(int x , int y , int ind)
{
    int p = log2[y - x + 1];
    if(r[ind][x][p] <= r[ind][y - (1 << p) + 1][p])
        return r[ind][x][p];
    return r[ind][y - (1 << p) + 1][p];
}
void path(int u)
{
    fr[u] = cnt;
    if(u != 1)
    {
        s[++ s[0]] = c[u];
        path(dad[u]);
    }
}
int get_z(int x , int y , int lca , int frx , int fry)
{
    return  min(query2(lca , x - 1 , frx) , query2(lca , y - 1 , fry));
}
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(muchii(i + 1 , y));
        G[i + 1].push_back(muchii(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 <= n ; i ++)
        if(G[i].size() == 1)
        {
            root = i;
            s[0] = 0;
            cnt ++;
            path(i);
            reverse(s + 1 , s + s[0] + 1);
            rmq2(r[cnt]);
        }
    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(lvl[x] , lvl[y] , lca , fr[t[x]] , fr[t[y]]);
        }
        xc = (xc * A + yc * B) % n + 1;
        yc = (yc * C + z * D) % n + 1;
        if(i > m - p)
            printf("%d\n" , z);
    }
    return 0;
}