제출 #839038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
839038		EntityPlantt	Fountain (eJOI20_fountain)	C++14	100 / 100	588 ms	38452 KiB

fountain

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
typedef int64_t ll;
const ll mxn = 100005, mxlogn = 18;
stack <pair <ll, ll>> falling;
vector <ll> children[mxn];
ll n, q, i, j, k, diameter, parent[mxn][mxlogn], cost[mxn][mxlogn], cost0[mxn];
ll jumpCost(ll index, ll len) {
    ll r = 0, start = index;
    for (ll k = 0; k < mxlogn; k++) {
        if (index < 0) return cost0[start];
        if (len & 1 << k) {
            r += cost[index][k];
            index = parent[index][k];
        }
    }
    return r;
}
ll jump(ll index, ll len) {
    for (ll k = 0; k < mxlogn; k++) {
        if (index < 0) return -1;
        if (len & 1 << k) index = parent[index][k];
    }
    return index;
}
void calcCost0(ll node, ll co) {
    cost0[node] = co;
    for (ll &x : children[node]) calcCost0(x, co + cost[x][0]);
}
int main() {
    cin >> n >> q;
    for (i = 0; i < n; i++) {
        for (j = 0; j < mxlogn; j++) parent[i][j] = -1;
        cin >> diameter >> cost[i][0];
        while (!falling.empty() && diameter > falling.top().first) {
            parent[falling.top().second][0] = i;
            children[i].push_back(falling.top().second);
            falling.pop();
        }
        falling.emplace(diameter, i);
    }
    while (!falling.empty()) {
        calcCost0(falling.top().second, cost[falling.top().second][0]);
        falling.pop();
    }
    for (j = 1; j < mxlogn; j++) {
        for (i = 0; i < n; i++) {
            if (parent[i][j - 1] >= 0 && parent[parent[i][j - 1]][j - 1] >= 0) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
                cost[i][j] = cost[i][j - 1] + cost[parent[i][j - 1]][j - 1];
            }
            else {
                cost[i][j] = cost0[i];
            }
        }
    }
    while (q--) {
        cin >> i >> j; i--;
        for (k = mxlogn - 1; k >= 0; k--) {
            if (i < 0) break;
            if (j > cost[i][k]) {
                j -= cost[i][k];
                i = parent[i][k];
            }
        }
        cout << ++i << '\n';
    }
    return 0;
}

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