AOC-2022-D7

#include <bits/stdc++.h>
using namespace std;

struct Node {
    string name;
    long long sz = 0;
    Node* parent;
    map<string,Node*> children;
    Node(string _n) : name(_n), sz(0LL), parent(nullptr), children() {}
};

void print(Node *node, int dep = 0) {
    if(!node) {
        return;
    }
    for(int i = 0; i < dep; i++) {
        cout << "--";
    }
    cout << '{' << node->name << ',' << node->sz << "}\n";
    for(pair<string,Node*> child : node->children) {
        print(child.second, dep + 1);
    }
}

map<Node*,long long> total_sz;

void dfs(Node *node) {
    if(!node) {
        return;
    }
    total_sz[node] = node->sz;
    for(pair<string,Node*> child : node->children) {
        dfs(child.second);
        total_sz[node] += total_sz[child.second];
    }
}

void clear(Node *node) {
    if(!node) {
        return;
    }
    for(pair<string,Node*> child : node->children) {
        clear(child.second);
    }
    free(node);
}

bool isNumber(string &s) {
    for(char ch : s) {
        if(ch < '0' || ch > '9') {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string line;
    Node *curr = nullptr;
    Node *head = nullptr;
    while(getline(cin, line)) {
        stringstream x(line);
        vector<string> words;
        string word;
        while(x.good()) {
            x >> word;
            words.push_back(word);
        }
        if(words[0] == "$") {
            if(words[1] == "cd") {
                if(curr == nullptr) {
                    curr = new Node(words[2]);
                    head = curr;
                }
                else if(words[2] == "..") {
                    curr = curr->parent;
                }
                else {
                    if(curr->children[words[2]]) {
                        curr = curr->children[words[2]];
                    }
                    else {
                        Node *new_node = new Node(words[2]);
                        curr->children[new_node->name] = new_node;
                        new_node->parent = curr;
                        curr = curr->children[words[2]];
                    }
                }
            }
        }
        else if(isNumber(words[0])) {
            curr->sz += stoll(words[0]);
        }
    }
    //print(head);
    dfs(head);
    //for(pair<Node*,long long> node : total_sz) {
    //  cout << '{' << node.first->name << ',' << node.second << "}\n";
    //}
    long long ans = 0LL;
    const long long MX = 100000LL;
    map<string, long long> score;
    for(pair<Node*,long long> node : total_sz) {
        score[node.first->name] = node.second;
        if(node.second <= MX) {
            ans += node.second;
        }
    }
    //for(auto p : score) {
    //  cerr << p.first << ": " << p.second << '\n';
    //}
    cout << "part1: ";
    cout << ans << '\n';
    long long req = 30000000LL - (70000000LL - total_sz[head]);
    long long mn = 1e18;
    for(pair<Node*,long long> node : total_sz) {
        if(node.second >= req) {
            mn = min(mn, node.second);
        }
    }
    cout << "part2: ";
    cout << mn << '\n';
    clear(head);
    return 0;
}