85112024-01-20 03:04:59qertendBináris fa magassága (50 pont)cpp17Runtime error 0/50561ms6900 KiB
#include <iostream>
#include <cmath>
#include <array>
using namespace std;

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 =pow(2, treeDepth-layer);
    out.endNodesStart = ID*layerDif;
    out.endNodesEnd = ID*layerDif + layerDif-1;
    return out;
}

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;
    for (int i = start; i <= end; i++) {
        if (array[i].depth > max) max = array[i].depth;
    }
    return max;
}

int main() {
    int treeDepth, M;
    cin >> treeDepth;
    cin >> M;
    int longestBranch = 0;
    int arrayLength = pow(2, treeDepth)-1;
    int endNodesStart = pow(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; 
        allNodes[nodeID].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";
        flush(cout);
    }
}
SubtaskSumTestVerdictTimeMemory
base0/50
1Accepted0/03ms1876 KiB
2Runtime error0/06ms4260 KiB
3Runtime error0/23ms2672 KiB
4Runtime error0/23ms2824 KiB
5Runtime error0/23ms2964 KiB
6Runtime error0/23ms3172 KiB
7Runtime error0/33ms3272 KiB
8Runtime error0/33ms3224 KiB
9Runtime error0/33ms3632 KiB
10Runtime error0/33ms3756 KiB
11Runtime error0/223ms5816 KiB
12Runtime error0/221ms5892 KiB
13Runtime error0/221ms5824 KiB
14Time limit exceeded0/2561ms4072 KiB
15Runtime error0/221ms5828 KiB
16Runtime error0/26ms5836 KiB
17Runtime error0/27ms6080 KiB
18Runtime error0/26ms6024 KiB
19Runtime error0/26ms6300 KiB
20Runtime error0/321ms6232 KiB
21Runtime error0/321ms6484 KiB
22Runtime error0/326ms6900 KiB
23Runtime error0/323ms6736 KiB