Cod sursa(job #2857718)

Utilizator DooMeDCristian Alexutan DooMeD Data 26 februarie 2022 10:42:06
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 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];
	
		}
	
	}
	
	temp = min(temp, rmq[a][0]);
	temp = min(temp, rmq[b][0]);
	
	return temp;
	
}
	
 
	
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;
	
}