Cod sursa(job #1772991)

Utilizator mariakKapros Maria mariak Data 7 octombrie 2016 13:01:41
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.31 kb
///Input :
///T(V, E) tree with |V| = N, |E| = N - 1; edge U, V, C
/// M pair of nodes (x, y) generated fron given X, Y, Z, A, B, C, D
///X' = (X*A + Y*B) mod N + 1
///Y' = (Y*C + Z*D) mod N + 1
/// Output :
/// find for each pair (x, y) of nodes the edge with minimum cost
/// via path between (x and y)

/// Solution
/// 1. compute table P[1,N][1,logN] where P[i][j] is the edge with minimum value
///via root (i, 2^j-th ancestor of i)
/// 2. compute table Anc[1,N][1,logN] where Anc[i][j] is the 2^j-th ancestor of i
/// 3. the solution for each pair is min(Rmq(x, th(LCA(x, y))), Rmq(y, th(LCA(x, y))))

#include <bits/stdc++.h>
#define Nmax 32002
#define INF 2000000002
#define pii pair <int, int>
#define pb(x) push_back(x)
#define f first
#define s second
#define mp make_pair
FILE *fin  = freopen("atac.in", "r", stdin);
FILE *fout = freopen("atac.out", "w", stdout);

using namespace std;
int n, m, p, lvl[Nmax], Log[Nmax];
struct point
{
    int anc;
    int edg;
} P[16][Nmax], T[Nmax];
vector <pii> G[Nmax];
bitset <Nmax> vis;
int Min(int x, int y)
{
    return (x < y ? x : y);
}
void read()
{
    int x, c;
    scanf("%d %d %d", &n, &m, &p);
    for(int i = 1; i < n; ++ i)
    {
        scanf("%d %d", &x, &c);
        G[x].pb(mp(i + 1, c));
        G[i + 1].pb(mp(x, c));
    }
}
void process()
{
    int i, j;
    for(i = 0; (1 << i) <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            P[i][j].anc = -1, P[i][j].edg = INF;

    for(i = 0; (1 << i) <= n; ++ i)
        for(j = 1; j <= n; ++ j)
        {
            if(i == 0)
                P[0][j] = T[j];
            else if(P[i - 1][j].anc != -1)
            {
                P[i][j].anc = P[i - 1][P[i - 1][j].anc].anc;
                P[i][j].edg = Min(P[i - 1][j].edg, P[i - 1][P[i - 1][j].anc].edg);
            }
        }
}
void DFS(int x)
{
    vis.set(x);
    for(int i = 0; i < G[x].size(); ++ i)
    {
        int y = G[x][i].f;
        if(!vis.test(y))
        {
            T[y].anc = x, T[y].edg = G[x][i].s;
            lvl[y] = lvl[x] + 1;
            DFS(y);
        }
    }
}
int LCA(int x, int y)
{
    int i, j, z = INF;
    if(lvl[x] < lvl[y])
        swap(x, y);

    int log = Log[lvl[x]];

    for(i = log; i >= 0; -- i)
        if (lvl[x] - (1 << i) >= lvl[y])
        {
            z = Min(z, P[i][x].edg);
            x = P[i][x].anc;
        }
    if(x == y) return z;

    log = Log[lvl[x]];

    for(i = log; i >= 0; -- i)
        if (P[i][x].anc != -1 && P[i][x].anc != P[i][y].anc)
        {
            z = Min(z, P[i][x].edg);
            z = Min(z, P[i][y].edg);
            x = P[i][x].anc, y = P[i][y].anc;
        }
    z = Min(z, T[x].edg);
    z = Min(z, T[y].edg);
    return z;
}
void solution()
{
    int x, y, z, A, B, C, D, lca, i;
    /// Log[1] = 0;
    for(i = 2; i < Nmax; ++ i)
        Log[i] = Log[i / 2] + 1;

    lvl[1] = 1;
    DFS(1);
    scanf("%d %d %d %d %d %d", &x, &y, &A, &B, &C, &D);
    process();
    for(i = 1; i <= m; ++ i)
    {
        if(x == y)
            z = 0;
        else z = LCA(x, y);
        if(i > m - p)
            printf("%d\n", z);
        x = (int)(1LL * (x*A + y*B) % n) + 1;
        y = (int)(1LL * (y*C + z*D) % n) + 1;
    }
}
int main()
{
    read();
    solution();
    return 0;
}