oj.uz

Submission #624272

# Submission time Handle Problem Language Result Execution time Memory
624272 2022-08-07T15:59:28 Z leoC Fountain (eJOI20_fountain) C++17
30 / 100
 5 ms 1620 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Runtime error 5 ms 1620 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -