Submission #624273

#	Time	Username	Problem	Language	Result	Execution time	Memory
624273		leoC	Fountain (eJOI20_fountain)	C++17	30 / 100	4 ms	1620 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1000000007;
 
int nbF, nbQ;
int capacity[10000];
vector<int> flowFrom[10001];
int volTree[10000];
int ancestor[10001][13];
 
void treeMaker(int x, int prevVol) {
    volTree[x]=prevVol;
    for (auto id:flowFrom[x]) {
        ancestor[id][0]=x;
        treeMaker(id, prevVol+capacity[id]);
    }
}
 
int dichoSearch(int ori, int base, int tier, int volume) {
    if (tier>0) {
        if (volTree[ori]-volTree[ancestor[base][tier]]<volume) {
            if (ancestor[base][tier]==nbF) {
                return 0;
            }
        }
        if (volTree[ori]-volTree[ancestor[base][tier-1]]<volume) {
            return dichoSearch(ori, ancestor[base][tier-1], tier-1, volume);
        }
        return dichoSearch(ori, base, tier-1, volume);
    } else {
        if (volTree[ori]-volTree[base]<volume) {
            return base+1;
        } else {
            return ancestor[base][0]+1;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> nbF >> nbQ;
 
    stack<vector<int>> diameters;
    int d; cin >> d;
    diameters.push({d, 0});
    cin >> capacity[0];
 
    for (int i=1; i<nbF; i++) {
        int dia, cap;
        cin >> dia >> cap;
        capacity[i]=cap;
        while (!diameters.empty()) {
            if (diameters.top()[0]<dia) {
                flowFrom[i].push_back(diameters.top()[1]);
                diameters.pop();
            } else {
                break;
            }
        }
        diameters.push({dia, i});
    }
    while (!diameters.empty()) {
        flowFrom[nbF].push_back(diameters.top()[1]);
        diameters.pop();
    }
 
    int height=(int)ceil(log2(nbF));
    for (int i=0; i<=nbF; i++) {
        for (int j=0; j<=height; j++) {
            ancestor[i][j]=nbF;
        }
    }
 
    treeMaker(nbF, 0);
 
    for (int k=1; k<=height; k++) {
        for (int v=0; v<=nbF; v++) {
            ancestor[v][k]=ancestor[ancestor[v][k-1]][k-1];
        }
    }
 
    for (int i=0; i<nbQ; i++) {
        int indx, vol;
        cin >> indx >> vol;
        indx--;
        cout << dichoSearch(indx, indx, height, vol) << endl;
    }
}

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