Cod sursa(job #2857123)

Utilizator DooMeDCristian Alexutan DooMeD Data 24 februarie 2022 21:42:51
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.48 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 up[nmax+5][lg+5], rmq[nmax+5][lg+5];
int niv[nmax+5];
bool viz[nmax+5];

void dfs(int node) {
	viz[node] = true;
	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(!viz[i.first]) {
			niv[i.first] = niv[node] + 1;
			up[i.first][0] = node;
			rmq[i.first][0] = i.second;
			dfs(i.first);
		}
	}
}

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

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