Cod sursa(job #1547325)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 decembrie 2015 12:00:57
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <iostream>
#include <utility>
#include <cmath>
#include <vector>
#include <array>
using namespace std;

constexpr int maxniv = 20;

struct muc{ int catre, cost; };

void dfs(const int cur, const int prev, const int cost_prev, const vector<vector<muc>>& arb,
	vector<array<int, maxniv>>& par_binar, vector<array<int, maxniv>>& min_binar, vector<int>& adanc){

	par_binar[cur][0] = prev;
	for(int niv = 1; niv < maxniv; ++niv){
		par_binar[cur][niv] = par_binar[par_binar[cur][niv-1]][niv-1]; }

	min_binar[cur][0] = cost_prev;
	for(int niv = 1; niv < maxniv; ++niv){
		min_binar[cur][niv] = min(min_binar[cur][niv-1], min_binar[par_binar[cur][niv-1]][niv-1]); }

	for(const auto next : arb[cur]){
		if(next.catre != prev){
			adanc[next.catre] = adanc[cur]+1;
			dfs(next.catre, cur, next.cost, arb, par_binar, min_binar, adanc); } } }

int minim_intre(int a, int b, const vector<int>& adanc,
	const vector<array<int, maxniv>>& par_binar, const vector<array<int, maxniv>>& min_binar){

	if(adanc[a] < adanc[b]){
		swap(a, b); }

	int rez = 1000000;
	for(int niv = maxniv-1; niv >= 0; --niv){
		if(adanc[b] <= adanc[par_binar[a][niv]]){
			rez = min(rez, min_binar[a][niv]);
			a = par_binar[a][niv]; } }
	for(int niv = maxniv-1; niv >= 0; --niv){
		if(par_binar[a][niv] != par_binar[b][niv]){
			rez = min(rez, min_binar[a][niv]);
			rez = min(rez, min_binar[b][niv]);
			a = par_binar[a][niv];
			b = par_binar[b][niv]; } }
	if(a != b){
		rez = min(rez, min_binar[a][0]);
		rez = min(rez, min_binar[b][0]);
		a = par_binar[a][0];
		b = par_binar[b][0]; }
	return rez; }
	

int main(){
	ifstream f("atac.in");
	ofstream g("atac.out");
	int n, m, p;
	f >> n >> m >> p;
	vector<vector<muc>> arb(n);
	for(int i = 1, x, cst; i < n; ++i){
		f >> x >> cst;
		--x;
		arb[x].push_back((muc){i, cst});
		arb[i].push_back((muc){x, cst}); }

	vector<array<int, maxniv>> par_binar(n), min_binar(n);
	vector<int> adanc(n, 0);
	dfs(0, 0, 1000000, arb, par_binar, min_binar, adanc);

	vector<int> solutii(m, 0);
	int x, y, a, b, c, d;
	f >> x >> y >> a >> b >> c >> d;
	for(int i = 0; i < m; ++i){
		if(x == y){
			solutii[i] = 0; }
		else{
			solutii[i] = minim_intre(x-1, y-1, adanc, par_binar, min_binar); }

		int x_n = (x * a + y * b) % n + 1,
			y_n = (y * c + solutii[i] * d) % n + 1;
		x = x_n, y = y_n; }
	for(int i = m-p; i < m; ++i){
		g << solutii[i] << '\n'; }
	return 0; }