Cod sursa(job #1618119)

Utilizator qwertyuiTudor-Stefan Berbinschi qwertyui Data 27 februarie 2016 18:20:34
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

ifstream fin ("atac.in");
ofstream fout ("atac.out");

#define MAXN 32000
#define MAXLOG 15

vector < vector < pair <int,int> > > edge;
int father[MAXLOG][MAXN], DP[MAXLOG][MAXN];
int depth[MAXN];
int N, Q, P; int X, Y, A, B, C, D;

void initialize()
{
    edge.resize(N+1);
}
void DFS (int node)
{
    for (int i = 0; i < edge[node].size(); ++i)
    {
		if (father[0][node] = edge[node][i].first)
			continue;
        depth[edge[node][i].first] = depth[node] + 1;
        father[0][edge[node][i].first] = node;
        DP[0][edge[node][i].first] = edge[node][i].second;
        DFS(edge[node][i].first);
    }
}

int LCA (int x, int y)
{

	if (depth[x] < depth[y])
        swap(x,y);

	int log1,log2;
    for(log1 = 0; (1 << log1) < depth[x]; log1++);                       //
    for(log2 = 0; (1 << log2) < depth[y]; log2++);

    for (int i = log1; i >= 0; --i)
        if (depth[x] - (1<<i) >= depth[y])
			x = father[i][x];

    if (x == y)
		return 0;

	for (int i = log2; i >= 0; --i)
        if (father[i][x] != father[i][y] && father[i][x] != 0)
		{
			x = father[i][x];
			y = father[i][y];
		}

	return father[0][x];

}

int kAncestor (int x, int k)
{
    int logarithm;

    for (logarithm = 0;  (1<<logarithm) < k; ++logarithm);

    for (int i = logarithm; i >= 0 && k; --i)
		if (k >= (1<<i))
		{
            k -= (1<<i);
            x = father[i][x];
		}

	return x;

}

int RMQ (int x, int y)
{
    if (depth[x] == depth[y])
		return INT_MAX;

	if (depth[x] < depth[y])
		swap(x,y);

	int i;
	for (i = 0; (1<<i) <= depth[x] - depth[y]; ++i);
	--i;

	int middle = kAncestor(x, depth[x] - depth[y] - (1<<i));

    if (DP[i][x] > DP[i][middle])
		return DP[i][middle];

	return DP[i][x];

}

int query (int x, int y)
{
	if (x == y)
		return 0;

	int lca = LCA(X,Y);

	return min(RMQ(lca,x), RMQ(lca,y));

}



int main()
{
    fin >>N >>Q >>P;

    initialize();

    for (int i = 2; i <= N; ++i)
	{
        int y, c;
        fin >>y >>c;
        edge[i].push_back(make_pair(y,c));
        edge[y].push_back(make_pair(i, c));
	}

    fin >>X >>Y >>A >>B >>C >>D;

    depth[1] = 1;

	DFS(1);

	for (int i = 1; (1<<i) <= N; ++i)
		for (int j = 1; j <= N; ++j)
			father[i][j] = father[i-1][father[i-1][j]];

	for(int k = 1; (1 << k) <= N; ++k)
        for(int i = 1; i <= N; ++i)
            DP[k][i] = min(DP[k-1][i], DP[k-1][father[k-1][i]]);

	for(int i = 1; i <= Q; ++i)
	{
        int Z = query(X,Y);
        if(i >= Q - P + 1)
            fout <<Z << "\n";

        X = (X*A + Y*B)%N + 1;
        Y = (Y*C + Z*D)%N + 1;

    }


    return 0;
}