Cod sursa(job #2444691)

Utilizator EdyOnuEdy Onu EdyOnu Data 1 august 2019 07:00:21
Problema Stramosi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
// stramosi.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "pch.h"
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#define NMAX 250001
#define LNMAX 18
using namespace std;

int S[LNMAX][NMAX];
int ancestors[NMAX];

class Solver {

public:

	explicit Solver(string&& in, string&& out) {

		FILE* fin = fopen(in.c_str(), "r"), *fout = fopen(out.c_str(), "w");

		int Q;

		// read data
		fscanf(fin, "%d %d", &N, &Q);
		for (int i = 1; i <= N; ++i) {
			fscanf(fin, "%d", &ancestors[i]);
		}

		// do the dynamic programming magic :))
		__process();

		// answer the questions
		int P, X;
		while (Q--) {
			fscanf(fin, "%d %d", &X, &P);
			fprintf(fout, "%d\n", __solve(X, P));
		}
	}

private:

	int __lg(int number) const {
		return floor(log2(number));
	}

	void __process() {


		/*
			S[i][j] = the 2 ^ j ancestor of node i
			S[i][0] = ancestors[i]
			S[i][j] = S[S[i][j-1]][j-1] while S[i][j - 1] != 0
		*/

		//int log = __lg(N);
		for (int i = 1; i <= N; ++i) {
			// first ancestor is the father
			S[0][i] = ancestors[i];

			//calculate the second, the forth, ..., ancestor of node i as long as it exists
			for (int j = 1; j <= 18; ++j) {
				if (!S[j - 1][i]) {
					break;
				}
				S[j][i] = S[j - 1][S[j - 1][i]];
			}
		}

	}

	int __solve(int Q, int P) {

		for (int j = LNMAX; j >= 0 && Q; --j) {
			if (!(P & (1 << j))) {
				continue;
			}
			Q = S[j][Q];
		}

		return Q;
	}

	int N;
};


int main() {
	Solver{
		"stramosi.in",
		"stramosi.out"
	};
}