oj.uz

Submission #839012

# Submission time Handle Problem Language Result Execution time Memory
839012 2023-08-28T13:23:20 Z EntityPlantt Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 43340 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, diameter[mxn], parent[mxn][mxlogn], cost[mxn][mxlogn], cost0[mxn], l, r, m, a;
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;
        l = 0; r = n + 5; i--;
        while (l <= r) {
            m = l + r >> 1;
            #ifndef ONLINE_JUDGE
            printf("| l = %lld, r = %lld, m = %lld, cost = %lld\n", l, r, m, jumpCost(i, m));
            #endif
            if (jumpCost(i, m) >= j) r = m - 1;
            else { a = m; l = m + 1; }
        }
        cout << jump(i, a) + 1 << '\n';
    }
    return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:98:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |             m = l + r >> 1;
      |                 ~~^~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 40012 KB Output is correct
2 Correct 640 ms 37624 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 2 ms 2772 KB Output is correct
3 Correct 3 ms 2900 KB Output is correct
4 Correct 8 ms 2900 KB Output is correct
5 Correct 6 ms 3028 KB Output is correct
6 Correct 7 ms 3028 KB Output is correct
7 Correct 7 ms 2900 KB Output is correct
8 Correct 686 ms 40012 KB Output is correct
9 Correct 640 ms 37624 KB Output is correct
10 Correct 5 ms 2900 KB Output is correct
11 Correct 640 ms 22912 KB Output is correct
12 Correct 908 ms 43340 KB Output is correct
13 Execution timed out 1565 ms 38892 KB Time limit exceeded
14 Halted 0 ms 0 KB -