Cod sursa(job #2923098)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 11 septembrie 2022 15:57:49
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

const int NMAX=32005;
const int  NMAX1=20;

vector<int> v[NMAX];
int rmq[NMAX1][NMAX];
int t[NMAX1][NMAX];
int lev[NMAX];
int ti[NMAX];
int to[NMAX];
int n,m,kon;

bool ancestor(int x,int y)
{
    return ti[x]<=ti[y] && to[x]>=to[y];
}

void dfs(int x)
{
    ti[x]=++kon;
    for(auto i:v[x])
        dfs(i);
    to[x]=++kon;
}

void dfs2(int p, int x)
{
	lev[p]=x;
	for(auto i : v[p])
		dfs2(i,x+1);
}

void precalculare_min()
{
    int e,i;
	dfs2(1,0);
	for(e=1;(1<<e)<=n;e++)
	{
		for(i=1;i<=n;i++)
		{
			t[e][i]=t[e-1][t[e-1][i]];
			rmq[e][i]=min(rmq[e-1][i],rmq[e-1][t[e-1][i]]);
		}
	}
}

int solve(int x, int y)
{
    int kon=1e9,i,j,level;
    level=abs(lev[x]-lev[y]);
	if(lev[x]<lev[y])
		swap(x,y);
	for(i=0;i<20;i++)
	{
		if(level & (1<<i))
		{
			kon=min(kon,rmq[i][x]);
			x=t[i][x];
		}
	}
	for(i=20;i>=0;i--)
	{
		if(t[i][x]!=t[i][y])
		{
			kon=min(kon,rmq[i][x]);
			kon=min(kon,rmq[i][y]);
			x=t[i][x];
			y=t[i][y];
		}
	}
	if(x!=y)
	{
		kon=min(kon,rmq[0][x]);
		kon=min(kon,rmq[0][y]);
	}
	return kon;
}

int main()
{
	int p,i,j,x,y,a,b,c,d,z,hp;
	fin>>n >>m>>p;
	for(i=2;i<=n;i++)
	{
		fin>>x>>hp;
		v[x].push_back(i);
		rmq[0][i]=hp;
		t[0][i]=x;
	}
	precalculare_min();
	fin>>x>>y>>a>>b>>c>>d;
	for(i=1;i<=m;i++)
	{
	    if(x==y)
            z=0;
        else
            z=solve(x, y);
		if(i>m-p)
			fout<<z<<"\n";
		x=(x*a+y*b)%n+1;
		y=(y*c+z*d)%n+1;
	}
	return 0;
}