oj.uz

Submission #839034

# Submission time Handle Problem Language Result Execution time Memory
839034 2023-08-28T14:05:08 Z EntityPlantt Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 40216 KB 
#define ONLINE_JUDGE
#include <iostream>
#include <vector>
using namespace std;
typedef int64_t ll;
const ll mxn = 100005, mxlogn = 18;
vector <ll> falling, children[mxn];
ll n, q, i, j, k, diameter[mxn], 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++) {
        cin >> diameter[i] >> cost[i][0];
        for (j = 0; j < mxlogn; j++) parent[i][j] = -1;
    }
    #ifndef ONLINE_JUDGE
    cout << "> Creating tree\n";
    #endif
    for (i = 0; i < n; i++) {
        #ifndef ONLINE_JUDGE
        cout << "| i = " << i << ", falling = [";
        if (falling.empty()) cout << ']';
        else {
            for (ll &x : falling) cout << x << ", ";
            cout << "\b\b]";
        }
        #endif
        for (j = falling.size() - 1LL; j >= 0; j--) {
            if (diameter[falling[j]] < diameter[i]) {
                parent[falling[j]][0] = i;
                children[i].push_back(falling[j]);
                falling.erase(falling.begin() + j);
            }
        }
        #ifndef ONLINE_JUDGE
        cout << ", finished\n";
        #endif
        falling.push_back(i);
    }
    for (ll &x : falling) calcCost0(x, cost[x][0]);
    #ifndef ONLINE_JUDGE
    cout << "cost0 =";
    for (i = 0; i < n; i++) cout << ' ' << cost0[i];
    cout << "\n> Creating sparse tables\n";
    #endif
    for (j = 1; j < mxlogn; j++) {
        #ifndef ONLINE_JUDGE
        printf("| %7lldth parent", 1LL << j);
        #endif
        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];
            }
            #ifndef ONLINE_JUDGE
            printf(" %4lld", parent[i][j]);
            #endif
        }
        #ifndef ONLINE_JUDGE
        printf("\n| %7lldth cost  ", 1LL << j);
        for (i = 0; i < n; i++) {
            printf(" %4lld", cost[i][j]);
        }
        cout << '\n';
        #endif
    }
    #ifndef ONLINE_JUDGE
    cout << "Starting queries\n";
    #endif
    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 2 ms 2644 KB Output is correct
2 Correct 3 ms 2848 KB Output is correct
3 Correct 3 ms 2792 KB Output is correct
4 Correct 4 ms 2924 KB Output is correct
5 Correct 5 ms 3060 KB Output is correct
6 Correct 5 ms 3028 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 38288 KB Output is correct
2 Correct 437 ms 35520 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2848 KB Output is correct
3 Correct 3 ms 2792 KB Output is correct
4 Correct 4 ms 2924 KB Output is correct
5 Correct 5 ms 3060 KB Output is correct
6 Correct 5 ms 3028 KB Output is correct
7 Correct 5 ms 2900 KB Output is correct
8 Correct 399 ms 38288 KB Output is correct
9 Correct 437 ms 35520 KB Output is correct
10 Correct 5 ms 2920 KB Output is correct
11 Correct 543 ms 22132 KB Output is correct
12 Correct 597 ms 40216 KB Output is correct
13 Correct 1477 ms 38056 KB Output is correct
14 Correct 422 ms 38536 KB Output is correct
15 Execution timed out 1570 ms 33756 KB Time limit exceeded
16 Halted 0 ms 0 KB -