Submission #1350264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350264		rmielamud	Designated Cities (JOI19_designated_cities)	C++20	Compilation error	0 ms	0 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

#define short int32_t
#define int int64_t
#define long __int128_t

const int inf{numeric_limits<int>::max() / 4};

struct Edge {
    int to;
    int w;
    int w_rev;
};

short main() {
    #ifndef LOCAL
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
    #endif

    int n;
    cin >> n;

    if (n > 16) {
        println("not implemented");
        return 0;
    }

    vector<vector<Edge>> edges(n);
    int total_cost{0};

    for (int i{0}; i < n - 1; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        a--;
        b--;

        edges[a].push_back({b, c, d});
        edges[b].push_back({a, d, c});
        total_cost += c + d;
    }

    function<pair<bool, int>(int, int, int)> dfs = [&](int node, int parent, int mask) {
        bool has_selected{((mask >> node) & 1) == 1};
        int cost{0};

        for (auto [to, w, w_rev] : edges[node]) {
            if (to != parent) {
                auto [child_has_selected, child_cost]{dfs(to, node, mask)};

                if (child_has_selected) {
                    has_selected = true;
                    cost += w;
                }

                cost += child_cost;
            } else {
                cost += w;
            }
        }

        return pair{has_selected, cost};
    };

    vector<int> mask_anss(1 << n);
    vector<int> popcnt_anss(n + 1);
    vector<int> popcnt_best(n + 1);

    for (int mask{1}; mask < (1 << n); mask++) {
        for (int i{0}; i < n; i++) {
            if ((mask >> i) & 1) {
                mask_anss[mask] = dfs(i, -1, mask).second;

                if (mask_anss[mask] > popcnt_anss[__builtin_popcountll(mask)]) {
                    popcnt_anss[__builtin_popcountll(mask)] = mask_anss[mask];
                    popcnt_best[__builtin_popcountll(mask)] = mask;
                }

                break;
            }
        }
    }

    // for (int i{1}; i <= n; i++) {
        // for (int mask{1}; mask < (1 << n); mask++) {
        //     if (mask_anss[mask] == popcnt_anss[i] && __builtin_popcountll(mask) == i) {
                // println("count={} best_cost={} best_mask={}", i, popcnt_anss[i], popcnt_best[i]);
        //     }
        // }
    // }

    int q;
    cin >> q;

    for (int i{0}; i < q; i++) {
        int e;
        cin >> e;
        cout << total_cost - popcnt_anss[e] << "\n";
    }

    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int32_t main()':
designated_cities.cpp:27:9: error: 'println' was not declared in this scope; did you mean 'rintl'?
   27 |         println("not implemented");
      |         ^~~~~~~
      |         rintl