86022024-01-23 09:03:01AzukitsuBináris fa magassága (50 pont)cpp17Időlimit túllépés 20/50600ms10836 KiB
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int max_magassag(vector<int> fa, int length, int index) {
    if (index > length) {
        return 0;
    }
    int bal_index = index * 2;
    int jobb_index = bal_index + 1;
    return max(
               max_magassag(fa, length, bal_index) + fa[index],
               max_magassag(fa, length, jobb_index) + fa[index]
               );
}

int main()
{
    int N, M;
    cin >> N >> M;
    //cout << N << endl;
    int sum = 0;
    for (int i = 0; i < N; i++) {
        //cout << sum << " " << N << " " << i << endl;
        sum += pow(2, i);
    }
    //cout << sum << endl;
    vector<int> fa(sum+1, 1); //osszes elem hosszu, a szamok a magassagokat jelzik
    //cout << max_magassag(fa, sum, 1) << endl;
    int indexek[M];
    int valuek[M];
    for (int i = 0; i < M; i++) {
        int index, value;
        cin >> index >> value;
        indexek[i] = index;
        valuek[i] = value;
    }
    for (int i = 0; i < M; i++) {
        fa[indexek[i]] = valuek[i];
        cout << max_magassag(fa, sum, 1) - 1 << endl;
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base20/50
1Elfogadva0/03ms1812 KiB
2Időlimit túllépés0/0600ms9220 KiB
3Elfogadva2/24ms2324 KiB
4Elfogadva2/24ms2304 KiB
5Elfogadva2/24ms2428 KiB
6Elfogadva2/24ms2652 KiB
7Elfogadva3/312ms2888 KiB
8Elfogadva3/317ms2948 KiB
9Elfogadva3/335ms2956 KiB
10Elfogadva3/335ms2956 KiB
11Időlimit túllépés0/2566ms10044 KiB
12Időlimit túllépés0/2582ms10044 KiB
13Időlimit túllépés0/2550ms10096 KiB
14Időlimit túllépés0/2561ms10132 KiB
15Időlimit túllépés0/2565ms10284 KiB
16Időlimit túllépés0/2565ms10456 KiB
17Időlimit túllépés0/2565ms10556 KiB
18Időlimit túllépés0/2569ms10632 KiB
19Időlimit túllépés0/2574ms10504 KiB
20Időlimit túllépés0/3558ms10612 KiB
21Időlimit túllépés0/3569ms10592 KiB
22Időlimit túllépés0/3558ms10744 KiB
23Időlimit túllépés0/3578ms10836 KiB