89582024-02-08 01:48:53qertendBináris fa magassága (50 pont)cpp17Hibás válasz 0/50600ms7144 KiB
#include <iostream>
using namespace std;

long powerOf2(int exponent) {
    long out = 1;
    out <<= exponent;
    return out;
}

class Node {
    public:
        int distanceUp;
        long endNodesStart;
        long endNodesEnd;
        long depth;

        void init(long ID, int treeDepth) {
            int layer = 1;
            int tmp = ID;
            while (tmp >= 2) {
                tmp >>= 1;
                layer++;
            }
            distanceUp = 1;
            long layerDif = powerOf2(treeDepth-layer);
            endNodesStart = ID*layerDif;
            endNodesEnd = ID*layerDif + layerDif-1;
        }
};

/**
 * adds the change to end 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[], long start, long end) {
    int max = 0;
    int ID;
    for (long 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;
    long arrayLength = powerOf2(treeDepth)-1;
    long endNodesStart = powerOf2(treeDepth-1);
    //cerr << "before array\n";
    Node allNodes[arrayLength];
    //cerr << "after array\n";
    //create Nodes
    for (long i = 0; i < arrayLength; i++) {
        allNodes[i].init(i+1, treeDepth);
    }
    //cerr << "created nodes\n";
    //set default length for end Nodes
    for (long i = endNodesStart; i < arrayLength; i++) {
        allNodes[i].depth = treeDepth-1;
    }
    //cerr << "set default lengths\n";
    //read instructions from stdin
    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) {
            long 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";
        //cerr << i << "/" << M << "\r";
    }
}

/**
 * Node array[] as function parameter not an array??
*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Hibás válasz0/03ms1744 KiB
2Időlimit túllépés0/0600ms3184 KiB
3Hibás válasz0/23ms2160 KiB
4Hibás válasz0/23ms2372 KiB
5Hibás válasz0/23ms2624 KiB
6Hibás válasz0/23ms2796 KiB
7Hibás válasz0/33ms3012 KiB
8Hibás válasz0/33ms3092 KiB
9Hibás válasz0/33ms3096 KiB
10Hibás válasz0/33ms3116 KiB
11Időlimit túllépés0/2546ms7144 KiB
12Időlimit túllépés0/2560ms4324 KiB
13Időlimit túllépés0/2569ms4432 KiB
14Időlimit túllépés0/2560ms4384 KiB
15Időlimit túllépés0/2569ms4652 KiB
16Időlimit túllépés0/2552ms4700 KiB
17Időlimit túllépés0/2552ms4852 KiB
18Időlimit túllépés0/2565ms4584 KiB
19Időlimit túllépés0/2552ms4728 KiB
20Időlimit túllépés0/3574ms4780 KiB
21Időlimit túllépés0/3569ms4608 KiB
22Időlimit túllépés0/3532ms4624 KiB
23Időlimit túllépés0/3569ms4728 KiB