Cod sursa(job #2636932)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 20 iulie 2020 17:43:59
Problema Atac Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000;
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] , c[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 viz[NMAX + 5];
void dfs2(int u)
{
    int v , j;
    viz[u] = 1;
    for(j = 0 ; j < G[u].size() ; j ++)
    {
        v = G[u][j];
        if(!viz[v])
        {
            c[root][v] = min(c[root][u] , cst[u][v]);
            dfs2(v);
        }
    }
}
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);
        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 = 1 ; i <= n ; i ++)
        for(j = 1 ; j <= n ; j ++)
            c[i][j] = INF;
    for(root = 1 ; root <= n ; root ++)
    {
        dfs2(root);
        memset(viz , 0 , sizeof(viz));
    }
    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(c[t[x]][lca] , c[t[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;
}