Submission #1222119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222119		hasan_86	Fountain (eJOI20_fountain)	C++20	100 / 100	396 ms	37612 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e5 + 5;
const int maxlg = 20;

int D[maxn], C[maxn];

vector<int> adj[maxn];

int par[maxn][maxlg];
long long depth[maxn][maxlg +1];

void dfs(int x, int parent) {
    //cout << x << " " << par[x][0] << endl;
    for (int i = 1; i < maxlg; i++) {
        par[x][i] = par[par[x][i-1]][i -1];
    }
    depth[x][0] = C[x];
    for (int i = 1; i <= maxlg; i++) {
        depth[x][i] = min(depth[x][i-1] + depth[par[x][i-1]][i-1], (long long)(1e9) + 100);
    }

    for (int v : adj[x]) {
        if (v == parent)
            continue;
        //cout << x << " is father of " << v << endl;
        par[v][0] = x;
        dfs(v, x);
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    memset(depth, 31, sizeof(depth));

    int n, q;
    cin >> n >> q;
    C[0] = 1e9 +10;
    for (int i = 1; i <= n; i++) {
        cin >> D[i] >> C[i];
    }

    stack<pii> st;
    st.push(pii(0, 1e9));

    for (int i = n; i > 0; i--) {
        while (!st.empty() && st.top().second <= D[i])
            st.pop();
        if (st.top().second > D[i]) {
            int x = st.top().first;
            adj[i].push_back(x);
            adj[x].push_back(i);
        }
        st.push(pii(i, D[i]));
    }

    dfs(0, -1);

    for (int i = 0; i < q; i++) {
        int R, V;
        cin >> R >> V;

        for (int i = maxlg; i >= 0; i--) {
            //cout << R << " " << i << " " << par[R][i] << " " << depth[R][i] << endl;
            if (depth[R][i] < V) {
                V -= depth[R][i];
                R = par[R][i];
            }
        }
        cout << R << endl;
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40