Cod sursa(job #3039956)

Utilizator IaaanAnghel Georgian Bogdan Iaaan Data 29 martie 2023 09:08:05
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in ("arb.in");
ofstream out ("arb.out");

const int NMAX = 25e4;
const int QMAX = 5e5;

struct query
{
    int u, d, idx;
    bool operator < (const query aux) const
    {
        if (d == aux.d) return idx < aux.idx;
        return d < aux.d;
    }
};

int a[NMAX + 5];
int c[NMAX + 5];
int ans[QMAX + 5];
query Q[QMAX + 5];
vector<int>g[NMAX + 5];
int tin[NMAX + 5], tout[NMAX + 5];
int time;
vector<int>order;

void dfs (int u, int w = 0)
{
    tin[u] = ++time;
    order.push_back(u);
    for (int v : g[u])
    {
        if (v == w) continue;
        dfs(v, u);
        order.push_back(u);
    }
    tout[u] = ++time;
}

int main()
{
    int n;
    in >> n;

    for (int i=1; i<=n; i++)
        in >> a[i], c[i] = a[i];

    for (int i=2; i<=n; i++)
        {
            int p;
            in >> p;
            g[p].push_back(i);
            g[i].push_back(p);
        }

    dfs(1);

    int q;
    in >> q;

    for (int i=1; i<=q; i++)
        in >> Q[i].u >> Q[i].d, Q[i].d = min(Q[i].d, n), Q[i].idx = i;

    sort(Q+1, Q+q+1);
    Q[0].d = -1;

    int ptr = 0;


    for (int i=1; i<=q; i++)
        out << ans[i] << '\n';

    return 0;
}