Cod sursa(job #2605526)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 25 aprilie 2020 12:50:45
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int INF = 1e9;
const int DIM = 32e3 + 7;
const int LOG = 20;

vector <pair <int, int> > adj[DIM];
int depth[DIM];
int val[DIM];
int dad[DIM][LOG + 1];
int rmq[DIM][LOG + 1];
int lca[DIM * 2][LOG + 1];
int f[DIM];

int timer = 0;

void dfs(int nod, int low = 1, int prev = 0)
{
	lca[++timer][0] = nod;
	f[nod] = timer;
	
	depth[nod] = low;
	dad[nod][0] = prev;
	rmq[nod][0] = val[nod];
	
	for(int i = 1; i <= LOG; ++i)
	{
		dad[nod][i] = dad[dad[nod][i - 1]][i - 1];
		rmq[nod][i] = min(rmq[nod][i - 1], rmq[dad[nod][i - 1]][i - 1]);
	}
	
	for(auto i : adj[nod])
	{
		if(i.first == prev)
			continue;
			
		val[i.first] = i.second;
		dfs(i.first, low + 1, nod);
		
		lca[++timer][0] = nod;
	}
}

int get_lca(int x, int y)
{
	x = f[x];
	y = f[y];
	
	if(x > y)
		swap(x, y);
	
	int bit = log2(y - x + 1);
	
	if(depth[lca[x][bit]] < depth[lca[y - (1 << bit) + 1][bit]])
		return lca[x][bit];
	else
		return lca[y - (1 << bit) + 1][bit];
}

int get_ans(int x, int y)
{
	if(x == y)
		return INF;
	
	int ans = INF;
	
	for(int i = LOG; i >= 0; --i)
	{
		if(depth[dad[x][i]] >= depth[y])
		{
			ans = min(ans, rmq[x][i]);
			x = dad[x][i];
		}
	}
	
	return ans;
}

main()
{
	int n, q, p;
	fin >> n >> q >> p;
	
	for(int i = 2; i <= n; ++i)
	{
		int x, c;
		fin >> x >> c;
		
		adj[x].emplace_back(i, c);
		adj[i].emplace_back(x, c);
	}
	
	dfs(1);
	
	for(int bit = 1; (1 << bit) <= timer; ++bit)
		for(int i = 1; i + (1 << bit) - 1 <= timer; ++i)
			if(depth[lca[i][bit - 1]] < depth[lca[i + (1 << (bit - 1))][bit - 1]])
				lca[i][bit] = lca[i][bit - 1];
			else
				lca[i][bit] = lca[i + (1 << (bit - 1))][bit - 1];
		
	int x, y, a, b, c, d;
	fin >> x >> y >> a >> b >> c >> d;
	
	int prev = 0;
	
	for(int i = 1; i <= q; ++i)
	{
		int ans = INF;
		
		if(i != 1)
		{
			x = (x * 1LL * a + y * 1LL * b) % n + 1;
			y = (y * 1LL * c + prev * 1LL * d) % n + 1;
		}
		
		int god = get_lca(x, y);
		
		ans = min(get_ans(x, god), get_ans(y, god));
		
		if(ans == INF)
		{
			ans = 0;
		}
		
		if(i >= q - p + 1)
			fout << ans << '\n';
		
		prev = ans;
	}
}