Cod sursa(job #754108)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 31 mai 2012 18:44:30
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

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

const int N = 33000;
const int inf = 100000000;

int n, mm, pp, f[N], lg[N];
int niv[N], rmq[17][3*N], e[3*N], nr;
int p[17][N], m[17][N];
vector<pair<int, int> > g[N];
bool ver[N];

inline int max(const int &a, const int &b) {return a > b ? a : b;}
inline void swap(int &a, int &b) {a^=b; b^=a; a^=b;}

void df(const int &nod, const int &l) {
	vector<pair<int, int> >::iterator it;
	
	ver[nod] = true;
	niv[nod] = l;
	e[++nr] = nod;
	f[nod] = nr;
	
	for(it = g[nod].begin(); it!=g[nod].end(); ++it) if(!ver[it->first]) {
		
		p[0][it->first] = nod;
		m[0][it->first] = it->second;
		
		df(it->first, l + 1);
		e[++nr] = nod;
	}
}

void makeLCA() {
	int i, j;
	
	for(i = 1; i<=nr; ++i)
		rmq[0][i] = niv[e[i]];
	
	for(i = 1; 1<<i <= nr; ++i)
		for(j = 1; j<=nr - (1<<i) + 1; ++j)
			
			rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1<<(i - 1))]);
}

int nivLCA(int nod1, int nod2) {
	nod1 = f[nod1]; nod2 = f[nod2];
	if(nod1 > nod2)
		swap(nod1, nod2);
	
	int l = lg[nod2 - nod1 + 1];
	
	return min(rmq[l][nod1], rmq[l][nod2 - (1<<l) + 1]);
}

void makeMin() {
	int i, j;
	
	for(i = 1; 1<<i <= n; ++i)
		for(j = 1; j<=n; ++j) if(niv[j] > 1<<i) {
			
			p[i][j] = p[i-1][p[i-1][j]];
			
			m[i][j] = min(m[i - 1][j], m[i - 1][p[i - 1][j]]);
		}
}

int sm(int nod, int h) {
	if(h == 0)
		return 0;
	
	int l, mm = inf;
	
	while(h) {
		l = lg[h];
		
		mm = min(mm, m[l][nod]);
		nod = p[l][nod];
		h -= 1<<l;
	}
	
	return mm;
}

int q(int x, int y) {
	
	int nivl = nivLCA(x, y);
	
	return min(sm(x, niv[x] - nivl), sm(y, niv[y] - nivl));
}

int main() {
	int i, o, u, x, y, a, b, c, d, nx, ny, z;
	
	in >> n >> mm >> pp;
	
	for(i = 2; i<=n; ++i) {
		in >> o >> u;
		
		g[o].push_back(pair<int, int>(i, u));
		g[i].push_back(pair<int, int>(u, u));
	}
	
	df(1, 1);
	
	makeLCA();
	
	for(i = 2; i!=N; ++i)
		lg[i] = lg[i>>1] + 1;
	
	makeMin();
	
	in >> x >> y >> a >> b >> c >> d;
	/*
	for(i = 1; i<=mm; ++i) {
		
		z = q(x, y);
		
		if(i >= mm - pp + 1)
			out << z << "\n";
		
		nx = (x * a + y * b)%n + 1;
		ny = (y * c + z * d)%n + 1;
		
		x = nx; y = ny;
	}*/
	
	return 0;
}