Cod sursa(job #2231195)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 13 august 2018 14:04:30
Problema Stramosi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <iostream>
using namespace std;

constexpr int maxn = 250000 + 10;
constexpr int maxq = 300000 + 10;

const int nil = -1;
int query_p[maxq], ret[maxq], first_query[maxn], next_query[maxq], first_son[maxn], brother[maxn], st[maxn], *stp = st + maxn;

void dfs(int curr){
    *--stp = curr;

    for(int i = first_query[curr]; i != nil; i = next_query[i])
        ret[i] = (stp + query_p[i] < st + maxn ? stp[query_p[i]] : 0);

    for(int next = first_son[curr]; next != nil; next = brother[next])
        dfs(next);
    ++stp; }

int main(){
    ifstream f("stramosi.in");
    ofstream g("stramosi.out");

    int n, m;
    f >> n >> m;

    for(int i = 0; i <= n; ++i) first_son[i] = brother[i] = nil;
    for(int i = 0; i < m; ++i) first_query[i] = next_query[i] = nil;
    
    for(int i = 1, x; i <= n; ++i){
        f >> x;
        brother[i] = first_son[x];
        first_son[x] = i; }

    for(int i = 0, q; i < m; ++i){
        f >> q >> query_p[i];
        next_query[i] = first_query[q];
        first_query[q] = i; }

    dfs(0);

    for(int i = 0; i < m; ++i) g << ret[i] << '\n'; }