Cod sursa(job #2371319)

Utilizator JohnnyTTache Radu Ioan JohnnyT Data 6 martie 2019 17:09:59
Problema Stramosi Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <vector>
#include <fstream>

using namespace std;

const int MAX_N = 250001, MAX_LEV = 19;
vector< vector<int> > stramosi(MAX_LEV, vector<int>(MAX_N));

void Read(ifstream & fin, int n){
    for(int i = 1; i <= n; i++){
        fin >> stramosi[0][i];
    }
}

void Complete(int n){
    for(int i = 1; i < MAX_LEV; i++){
        for(int j = 1; j <= n; j++){
            stramosi[i][j] = stramosi[i-1][stramosi[i-1][j]];
        }
    }
}

void Resolve(ifstream & fin, ofstream & fout, int m){
    int q, p;
    for(int z = 0; z < m; ++z){
        fin >> q >> p;

        int ans = q;
        
        for(int pow = 0; (ans != 0) && (p > 0); p >>=1, ++pow ){
            if((p & 1) == 0){
                continue;
            }
            ans = stramosi[pow][ans];
        }
        fout << ans << endl;
    }
}

int main(){
    int n, m;
    ifstream fin{"stramosi.in"};
    ofstream fout{"stramosi.out"};
    fin >> n >> m;
    Read(fin, n);
    Complete(n);
    Resolve(fin, fout, m);
}