Submission #1208193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208193		kaltspielerhy	Fountain (eJOI20_fountain)	C++20	100 / 100	258 ms	48420 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define VIDE nbFontaines+1
const int INFINI = 1e17;

struct fontaine {
    int taille, contenance;
};

void dfs(int noeud, int parent, vector<vector<int>>& graphe, vector<vector<pair<int, int>>>& ancetres, vector<fontaine>& fontaines) {
    ancetres[noeud][0] = {parent, fontaines[noeud].contenance};

    for (int iBit = 1; iBit < 18; iBit++) {
        ancetres[noeud][iBit].first = ancetres[ancetres[noeud][iBit-1].first][iBit-1].first;
        ancetres[noeud][iBit].second = ancetres[noeud][iBit-1].second + ancetres[ancetres[noeud][iBit-1].first][iBit-1].second;
    }

    for (int iVoisin : graphe[noeud]) {
        if (iVoisin != parent) {
            dfs(iVoisin, noeud, graphe, ancetres, fontaines);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int nbFontaines, nbRequetes;
    cin >> nbFontaines >> nbRequetes;
    vector<fontaine> fontaines(nbFontaines);
    for (auto& it : fontaines) {
        cin >> it.taille >> it.contenance;
    }
    fontaines.push_back({INFINI, 0});

    // pour ne pas déclencher define
    vector<vector<int>> graphe(nbFontaines+1);

    vector<pair<int, int>> monotone;
    monotone.push_back({0, fontaines[0].taille});
    for (int i = 1; i <= nbFontaines; i++) {
        while (!monotone.empty() && monotone.back().second < fontaines[i].taille) {
            graphe[monotone.back().first].push_back(i);
            graphe[i].push_back(monotone.back().first);
            monotone.pop_back();
        }
        monotone.push_back({i, fontaines[i].taille});
    }

    while (!monotone.empty()) {
        graphe[monotone.back().first].push_back(nbFontaines);
        graphe[nbFontaines].push_back(monotone.back().first);
        monotone.pop_back();
    }

    // nbFontaines+1 est une place vide
    vector<vector<pair<int, int>>> ancetres(nbFontaines+2, vector<pair<int, int>>(18, {VIDE, INFINI}));
    for (int i = 0; i < 18; i++) ancetres[VIDE][i] = {nbFontaines+1, 0};
    dfs(nbFontaines, VIDE, graphe, ancetres, fontaines);

    for (int iRequete = 0; iRequete < nbRequetes; iRequete++) {
        int depart, capacite;
        cin >> depart >> capacite;
        depart--;

        int bitD = 17;
        while (bitD >= 0) {
            while (bitD >= 0 && (ancetres[depart][bitD].first == VIDE || ancetres[depart][bitD].second >= capacite)) {
                bitD--;
            }
            if (bitD < 0) break;
            capacite -= ancetres[depart][bitD].second;
            depart = ancetres[depart][bitD].first;
            bitD--;
        }

        cout << (depart+1)%(nbFontaines+1) << '\n';
    }

    return 0;
}

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