oj.uz

Submission #839038

# Submission time Handle Problem Language Result Execution time Memory
839038 2023-08-28T14:20:15 Z EntityPlantt Fountain (eJOI20_fountain) C++14
100 / 100
 588 ms 38452 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 4 ms 2980 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 36440 KB Output is correct
2 Correct 426 ms 33764 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 4 ms 2980 KB Output is correct
5 Correct 5 ms 2900 KB Output is correct
6 Correct 5 ms 2900 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 385 ms 36440 KB Output is correct
9 Correct 426 ms 33764 KB Output is correct
10 Correct 4 ms 2900 KB Output is correct
11 Correct 211 ms 20724 KB Output is correct
12 Correct 588 ms 38452 KB Output is correct
13 Correct 475 ms 35420 KB Output is correct
14 Correct 413 ms 34992 KB Output is correct
15 Correct 388 ms 36612 KB Output is correct