Cod sursa(job #1861314)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 28 ianuarie 2017 19:28:17
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <stack>
#include <bitset>
#include <cctype>
#include <set>
#define MOD 9973
#define pb push_back
#define INF 0x3f3f3f3f
#define INFLL (1LL*INF*INF)
#define ll long long
#define LOGMAX 16
#define NMAX 32005

using namespace std;

typedef pair<int, int> pii;

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

int cost[LOGMAX][NMAX],anc[LOGMAX][NMAX],d[NMAX],depthmax;
vector<int> v[NMAX];

void DFS(int x, int depth) {
	depthmax=max(depthmax,depth);
	d[x]=depth;
	for(auto it:v[x])
		DFS(it,depth+1);
}

int ansquery(int x, int y) {
	int dif,i,minact;
	if(d[x]>d[y]) swap(x,y);

	dif=d[y]-d[x];

	minact=INF;
	for(i=0;(1<<i)<=dif;++i) {
		if(dif&(1<<i)) {
			minact=min(minact,cost[i][y]);
			y=anc[i][y];
		}
	}

	for(i=LOGMAX;i>=0;--i) {
		if(anc[i][x]!=anc[i][y]) {
			minact=min(minact,min(cost[i][x],cost[i][y]));
			x=anc[i][x];
			y=anc[i][y];
		}
	}

	if(x!=y) minact=min(minact,min(cost[0][x],cost[0][y]));

	return minact;
}

int main() {
	int i,n,m,nr,aux,auxst,auxdr,pos,x,p,y,j,a,b,c,d,z,xaux,yaux;

	fin>>n>>m>>p;

	for(i=2;i<=n;++i) {
		fin>>x>>y;
		v[x].pb(i);
		anc[0][i]=x;
		cost[0][i]=y;
	}

	DFS(1,0);

	for(i=1;(1<<i)<=depthmax;++i) {
		for(j=1;j<=n;++j) {
			anc[i][j]=anc[i-1][anc[i-1][j]];
			cost[i][j]=min(cost[i-1][j],cost[i-1][anc[i-1][j]]);
		}
	}

	fin>>x>>y>>a>>b>>c>>d;
	for(i=1;i<=m;++i) {
		z=ansquery(x,y);

		if(i>=m-p+1) fout<<z<<'\n';

		xaux=(x*a+y*b)%n+1;
		yaux=(y*c+z*d)%n+1;
		x=xaux;
		y=yaux;
	}

	return 0;
}