Cod sursa(job #1488725)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 19 septembrie 2015 17:23:05
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define F first
#define S second
#define PII pair < int , int >

using namespace std;

const int Nmax = 32000 + 10;

int n , m , p , i , cost , k , x;
int node1 , node2 , z , A , B , C , D;
int first[Nmax] , Log[Nmax] , lvl[Nmax];
int dp[Nmax][17] , tata[Nmax][17];

vector < int > v;
vector < PII > g[Nmax];
vector < PII > d[18];

void euler(int node , int lvl , int dad)
{
    d[0].push_back({lvl , node});
    first[node] = d[0].size() - 1;

    for (auto &it : g[node])
    {
        if (it.F == dad) continue;
        euler(it.F , lvl+1 , node);
        d[0].push_back({lvl , node});
    }
}

void makeRmq()
{
    int i , j , n = d[0].size() - 1;

    for (i = 2; i <= n; ++i) Log[i] = Log[i>>1] + 1;

    for (i = 1; i <= Log[n]; ++i)
    {
        d[i].push_back({0,0});
        for (j = 1; j <= n - (1<<i) + 1; ++j)
        {
            d[i].push_back({0,0});
            d[i][j] = (d[i-1][j].F <= d[i-1][j+(1<<(i-1))].F) ? d[i-1][j] : d[i-1][j+(1<<(i-1))];
        }
    }
}

void dfs(int node ,  int price , int level , int dad)
{
    lvl[node] = level;

    ///dinamica
    int nr;
    dp[node][0] = price; tata[node][0] = dad;
    for (nr = 1; (1 << nr) <= v.size(); nr++)
        dp[node][nr] = min(dp[node][nr-1] , dp[tata[node][nr-1]][nr-1]),
        tata[node][nr] = v[v.size()-(1<<nr)];
    ///

    for (auto &it : g[node])
    {
        if (it.F == dad) continue;
        v.push_back(it.F);
        dfs(it.F , it.S , level + 1 , node);
        v.pop_back();
    }
}

int ans(int x , int y)
{
    if (lvl[x] >= lvl[y]) return inf;
    int k = Log[lvl[x]-lvl[y]];
    return (min(dp[x][k] , ans(tata[x][k] , y)));
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("atac.in","r",stdin);
    freopen("atac.out","w",stdout);
    #endif

    scanf("%d %d %d", &n, &m, &p);
    for (i = 2; i <= n; ++i)
    {
        scanf("%d %d", &x, &cost);
        g[x].push_back({i , cost});
        g[i].push_back({x , cost});

    }
    scanf("%d %d %d %d %d %d", &node1, &node2, &A, &B, &C, &D);

    euler(1 , 1 , 0);
    makeRmq();
    v.push_back(1); memset(dp[1] , inf , sizeof(dp[1]));
    dfs(1 , 1 , 0 , 0);

    for (i = 1; i <= m; ++i)
    {
        ///lca
        int left = first[node1]; int right = first[node2];
        if (left > right) swap(left , right);
        k = Log[right - left + 1];
        int lca = (d[k][left].F < d[k][right-(1<<k)+1].F) ? d[k][left].S : d[k][right-(1<<k)+1].S;
        ///

        z = min(ans(node1 , lca) , ans(node2 , lca));

        if (m - i + 1 <= p) printf("%d\n", z);

        node1 = (node1 * A + node2 * B) % n + 1;
        node2 = (node2 * C + z * D) % n + 1;
    }

    return 0;
}