Cod sursa(job #1547305)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 decembrie 2015 11:30:42
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.43 kb
#include <fstream>
#include <iostream>
#include <utility>
#include <cmath>
#include <vector>
#include <array>
using namespace std;

constexpr int maxniv = 20;

template <typename T, typename Cmp>
class rmq{
	int n;
	vector<array<int, maxniv>> buf;
	Cmp cmp;
public:
	rmq(const vector<T>& v, Cmp c): n(v.size()), buf(n), cmp(c){
		for(int i = 0; i < n; ++i){
			buf[i][0] = v[i]; }
		for(int niv = 1, step = 1; niv < maxniv; ++niv, step *= 2){
			for(int st = 0, dr = step; dr < n; ++st, ++dr){
				buf[st][niv] = min(buf[st][niv-1], buf[dr][niv-1], cmp); } } }
	T query(int st, int dr)const{
		const int niv = log2(dr-st+1), step = 1<<niv;
		return min(buf[st][niv], buf[dr-step+1][niv], cmp); } };

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>& euler, vector<int>& firsts, vector<int>& adanc){

	euler.push_back(cur);
	firsts[cur] = euler.size()-1;

	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, euler, firsts, adanc);
			euler.push_back(cur); } } }

class vec_comp{
	vector<int>& v;
public:
	vec_comp(vector<int>& V): v(V){}
	bool operator()(const int st, const int dr)const{
		return v[st] < v[dr]; } };

using lca_rmq = rmq<int, vec_comp>;

int min_sus(int jos, const int sus, const vector<int>& adanc, const vector<array<int, maxniv>>& par_binar,
	const vector<array<int, maxniv>>& min_binar){
	int rez = min_binar[jos][0];
	for(int niv = 0, d_adanc = adanc[jos] - adanc[sus]; d_adanc > 0; d_adanc /= 2, ++niv){
		if(d_adanc%2 == 1){
			rez = min(rez, min_binar[jos][niv]);
			jos = par_binar[jos][niv]; } }
	return rez; }

int minim_intre(const int a, const int b, const vector<int>& adanc, const vector<int>& firsts,
	const lca_rmq& for_lca, const vector<array<int, maxniv>>& par_binar,
	const vector<array<int, maxniv>>& min_binar){
	int lca;
	{
		int A = firsts[a], B = firsts[b];
		if(A > B){
			swap(A, B); }
		lca = for_lca.query(A, B); }
	return min(min_sus(a, lca, adanc, par_binar, min_binar), min_sus(b, lca, adanc, par_binar, min_binar));}
	

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> euler, firsts(n, 0), adanc(n, 0);
	dfs(0, 0, 1000000, arb, par_binar, min_binar, euler, firsts, adanc);

	vec_comp vc(adanc);

	lca_rmq for_lca(euler, vc);
	
	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){
		solutii[i] = minim_intre(x-1, y-1, adanc, firsts, for_lca, 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; }