Submission #1019421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019421		coolboy19521	Fountain (eJOI20_fountain)	C++17	0 / 100	149 ms	28112 KiB

fountain

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>

using namespace std;

const int MAX_N = 1e5 + 5;
const int LOG = 25;
const long long inf = 1e18 + 18;

vector<int> adj[MAX_N]; // Adjacency list for the tree
long long prefixSum[MAX_N]; // prefixSum to store the water capacity sums
int depth[MAX_N]; // to store depth of each node (can be useful for debugging)
int ancestor[LOG][MAX_N]; // Sparse table for ancestors

// Depth-First Search to setup ancestor table and compute prefix sums
void dfs(int node, int parent = 0, long long sum = 0) {
    ancestor[0][node] = parent;
    prefixSum[node] = sum;
    depth[node] = depth[parent] + 1;

    for (int i = 1; i < LOG; ++i) {
        ancestor[i][node] = ancestor[i-1][ancestor[i-1][node]];
    }

    for (int child : adj[node]) {
        if (child != parent) {
            dfs(child, node, sum + depth[child]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<pair<int, int>> nodes;

    for (int i = 1; i <= n; ++i) {
        int d, c;
        cin >> d >> c;
        depth[i] = c; // using depth array temporarily to store capacity
        nodes.emplace_back(d, i);
    }

    // Sort nodes based on 'd' value
    sort(nodes.begin(), nodes.end());

    // Tree construction
    set<int> roots;
    roots.insert(n + 1); // artificial root

    for (auto it = nodes.rbegin(); it != nodes.rend(); ++it) {
        int current = it->second;
        auto parent = roots.upper_bound(current);
        adj[*parent].push_back(current);
        roots.insert(current);
    }

    // Initialize DFS from the artificial root
    dfs(n + 1);

    while (q--) {
        int r, v;
        cin >> r >> v;
        int answer = r;

        for (int i = LOG - 1; i >= 0; --i) {
            if (prefixSum[answer] - prefixSum[ancestor[i][answer]] + depth[ancestor[i][answer]] < v) {
                answer = ancestor[i][answer];
            }
        }

        // Final check if the direct parent satisfies the condition
        if (prefixSum[answer] - prefixSum[ancestor[0][answer]] + depth[ancestor[0][answer]] < v) {
            answer = ancestor[0][answer];
        }

        // Check if reached the root
        if (answer == n + 1) {
            answer = 0;
        }

        cout << answer << '\n';
    }

    return 0;
}

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