85852024-01-22 12:59:49qertendBináris fa magassága (50 pont)cpp17Futási hiba 0/50550ms5964 KiB
#include <iostream>
using namespace std;

int power(int base, int exponent) {
    int out = base;
    while (exponent > 1) {
        out *= base;
        exponent--;
    }
    if (exponent == 0) out = 1;
    return out;
}

struct Node {
    int distanceUp;
    int endNodesStart;
    int endNodesEnd;
    int depth;
};

Node newNode(int ID, int treeDepth) {
    int layer = 1;
    float tmp = ID;
    while (tmp >= 2) {
        tmp /= 2;
        layer++;
    }
    Node out;
    out.distanceUp = 1;
    int layerDif =power(2, treeDepth-layer);
    out.endNodesStart = ID*layerDif;
    out.endNodesEnd = ID*layerDif + layerDif-1;
    return out;
}
/**
 * adds the change to all nodes from start to end (inclusive)
*/
void updateDepth(int change, Node array[], int start, int end) {
    for (int i = start; i <= end; i++) {
        array[i].depth += change;
    }
}

int max(Node array[], int start, int end) {
    int max = 0;
    int ID;
    for (int i = start; i <= end; i++) {
        if (array[i].depth > max) {
            max = array[i].depth;
            ID = i;
        }
    }
    return max;
}

int main() {
    int treeDepth, M;
    cin >> treeDepth;
    cin >> M;
    int longestBranch = 0;
    int arrayLength = power(2, treeDepth)-1;
    int endNodesStart = power(2, treeDepth-1);
    Node allNodes[arrayLength];
    //create Nodes
    for (int i = 0; i < arrayLength; i++) {
        allNodes[i] = newNode(i+1, treeDepth);
    }
    //set default length for end Nodes
    for (int i = endNodesStart; i < arrayLength; i++) {
        allNodes[i].depth = treeDepth-1;
    }
    //read instructions
    for (int i = 0; i < M; i++) {
        int newDistance, nodeID;
        cin >> nodeID;
        nodeID--;
        cin >> newDistance;
        Node &modifiedNode = allNodes[nodeID];
        int change = newDistance-modifiedNode.distanceUp; 
        modifiedNode.distanceUp = newDistance;
        updateDepth(change, allNodes, modifiedNode.endNodesStart, modifiedNode.endNodesEnd);
        if (change > 0) {
            int currentHeight = max(allNodes, modifiedNode.endNodesStart, modifiedNode.endNodesEnd);
            if (currentHeight > longestBranch) longestBranch = currentHeight;
        }
        else if (change < 0) {
            longestBranch = max(allNodes, endNodesStart, arrayLength-1);
        }
        cout << longestBranch << "\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Elfogadva0/03ms1880 KiB
2Futási hiba0/04ms4220 KiB
3Futási hiba0/23ms2388 KiB
4Futási hiba0/23ms2880 KiB
5Futási hiba0/23ms2752 KiB
6Futási hiba0/23ms2792 KiB
7Futási hiba0/33ms2816 KiB
8Futási hiba0/33ms3076 KiB
9Futási hiba0/33ms3028 KiB
10Futási hiba0/33ms3032 KiB
11Futási hiba0/220ms5072 KiB
12Futási hiba0/220ms5328 KiB
13Futási hiba0/230ms5304 KiB
14Időlimit túllépés0/2550ms3508 KiB
15Futási hiba0/220ms5540 KiB
16Futási hiba0/24ms5480 KiB
17Futási hiba0/24ms5760 KiB
18Futási hiba0/24ms5696 KiB
19Futási hiba0/24ms5848 KiB
20Futási hiba0/329ms5804 KiB
21Futási hiba0/330ms5804 KiB
22Futási hiba0/324ms5964 KiB
23Futási hiba0/321ms5904 KiB