utgarda · January 18, 2015 18:13 · Jan 18, 2015 · Jan 18, 2015
diff --git a/gifts → gifts.cpp b/gifts → gifts.cpp
diff --git a/gifts b/gifts
@@ -0,0 +1,118 @@
+#include <iostream>
+#include <vector>
+#include <unordered_map>
+using namespace std;
+
+struct Tree {
+        int value;
+        Tree(int v) : value(v) {}
+        vector<Tree*> c;
+};
+
+
+void print(Tree* t, int depth = 0) {
+        for (int i = 0; i < depth; ++i)
+                cout << '\t';
+        cout << t->value << endl;
+        for (Tree* c : t->c) {
+                print(c, depth + 1);
+        }
+}
+
+Tree* gen_tree(vector<int>& v) {
+        Tree* root = NULL;
+        unordered_map<int, Tree*> nodes;
+        for (int i = 0; i < v.size(); ++i) {
+                int ind = i + 1;
+                if (v[i] == 0) {
+                        root = new Tree(1);
+                        nodes[ind] = root;
+                } else {
+                        auto node = new Tree(ind);
+                        auto parent = nodes[v[i]];
+                        parent->c.push_back(node);
+                        nodes[ind] = node;
+                }
+        }
+        //print(root);
+        return root;
+}
+
+typedef std::pair<int, int> Ret;
+
+
+
+
+unordered_map<int, vector<Ret>> cache;
+
+
+Ret from_cache(Tree* t, int ban) {
+        vector<Ret>& rets(cache[t->value]);
+        for (Ret ret : rets) {
+                if (ret.second != ban)
+                        return ret;
+        }
+        throw runtime_error("???");
+}
+
+
+Ret solve(Tree* t, int ban_gift = 0) {
+//      cout << "solve node: " << t->value << " ban_gift:" << ban_gift << endl;
+        if (t->c.empty()) {
+                if (ban_gift == 1) {
+                        return Ret(2, 2);
+                } else
+                        return Ret(1, 1);
+        }
+        if (cache.find(t->value) != cache.end()) {
+                //cout << "cache hit!" << endl;
+                return from_cache(t, ban_gift);
+        }
+        int gift = 1;
+        int min_sum = -1;
+        int min_gift = -1;
+        int max_c_gift = 1;
+        vector<Ret> rets;
+        do {
+                int sum = gift;
+                for (auto c : t->c) {
+                        auto ret = solve(c, gift);
+                        sum += ret.first;
+                        max_c_gift = max(max_c_gift, ret.second);
+                }
+                if (min_sum == -1 || sum < min_sum) {
+                        min_sum = sum;
+                        min_gift = gift;
+                }
+                rets.push_back(Ret(sum, gift));
+                ++gift;
+        } while (gift <= max_c_gift + 1);
+        sort(rets.begin(), rets.end());
+        cache[t->value] = rets;
+        return from_cache(t, ban_gift);
+}
+
+
+int main(int c, char* argv[]) {
+        int t;
+        cin >> t;
+        for (int i = 0; i < t; ++i) {
+                int n;
+                cin >> n;
+                vector<int> v;
+                for (int k = 0; k < n; ++k) {
+                        int l;
+                        cin >> l;
+                        v.push_back(l);
+                }
+
+                Tree* t = gen_tree(v);
+                cache.clear();
+                auto ret = solve(t);
+                /*auto rets = cache[1];
+                for (auto r : rets) {
+                        cout << "sum: " << r.first << " CEO gift:" << r.second << endl;
+                }*/
+                cout << "Case #" << (i+1) << ": " << ret.first << endl;
+        }
+}