Cod sursa(job #2857115)

Utilizator DooMeDCristian Alexutan DooMeD Data 24 februarie 2022 21:33:13
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax = 32000;
const int lg = 15;

vector<vector<pair<int,int>>> dx(nmax+5);
int niv[nmax+5];
int up[nmax+5][lg+5], rmq[nmax+5][lg+5];

void dfs(int node, int ant) {
	for(int i=1; i<=lg; i++)
		up[node][i] = up[up[node][i-1]][i-1];
	for(int i=1; i<=lg; i++)
		rmq[node][i] = min(rmq[node][i-1], rmq[up[node][i-1]][i-1]);
	for(auto i : dx[node]) {
		if(i.first!=ant) {
			niv[i.first] = niv[node] + 1;
			up[i.first][0] = node;
			rmq[i.first][0] = i.second;
			dfs(i.first,node);
		}
	}
}

int query(int a, int b) {
	if(niv[a] < niv[b]) swap(a,b);
	int temp = 1e9;
	for(int i=lg; i>=0; i--)
		if(niv[up[a][i]]>=niv[b]) {
			temp = min(temp, rmq[a][i]);
			a = up[a][i];
		}
	if(a==b) return temp;
	for(int i=lg; i>=0; i--) {
		if(up[a][i]!=up[b][i]) {
			temp = min(temp, rmq[a][i]);
			temp = min(temp, rmq[b][i]);
			a = up[a][i];
			b = up[b][i];
		}
	}
	return min(temp, min(rmq[a][0], rmq[b][0]));
}

int main () { 
	ifstream f("atac.in");
	ofstream g("atac.out");
	
	int n,q,p; f >> n >> q >> p;
	for(int x=2; x<=n; x++) {
		int y,w; f >> y >> w;
		dx[x].emplace_back(y,w);
		dx[y].emplace_back(x,w);
	}
	niv[1] = 1;
	dfs(1, 0);
	int x,y,a,b,c,d,z; f >> x >> y >> a >> b >> c >> d;
	vector<int> ans(q+5);
	for(int i=1; i<=q; i++) {
		if(x==y) z = 0;
		else z = query(x,y);
		ans[i] = z;
		x = (x*a + y*a) % n + 1;
		y = (y*c + z*d) % n + 1;
	}
	for(int i=q-p+1; i<=q; i++) g << ans[i] << "\n";
	return 0;
}