Submission #318501

#	Time	Username	Problem	Language	Result	Execution time	Memory
318501		qpwoeirut	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	492 KiB

beads

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MN = 11;

void chmx(ll& a, ll b) {if (a<b) a=b;}

struct Edge {
    int from, to;
    ll len;

    Edge() {
        from = to = len = 0;
    }
    Edge(int _from, int _to, ll _len) {
        from = _from;
        to = _to;
        len = _len;
    }

    inline const bool operator<(const Edge& other) const {
        if (len != other.len) {
            return len < other.len;
        }
        if (from != other.from) {
            return from < other.from;
        }
        return to < other.to;
    }
    inline const bool operator>(const Edge& other) const {
        return other < *this;
    }
};

int N;
set<Edge> adj[MN];
bool leaf[MN], real_leaf[MN];

int dfs(int node, int par) {
    int ret = 1;
    for (auto it=adj[node].begin(); it!=adj[node].end(); ++it) {
        if (it->to == par) continue;
        ret += dfs(it->to, node);
    }
    return ret;
}

bool works() {
    for (int i=0; i<N; ++i) {
        leaf[i] = adj[i].size() == 1;
    }

    bool two = false;
    for (int i=0; i<N; ++i) {
        int leaf_ct = 0;
        int real_ct = 0;
        for (auto it=adj[i].begin(); it!=adj[i].end(); ++it ){
            if (leaf[it->to]) {
                ++leaf_ct;
            }
            if (real_leaf[it->to]) {
                ++real_ct;
            }
        }

        if (leaf_ct >= 3) return false;
        if (real_ct >= 2) {
            if (two) return false;
            two = true;
        }
        if ((dfs(i, -1) & 1) == 0) return false;
    }


    return true;
}

Edge edge[MN];
int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N;
    for (int i=0; i<N-1; ++i) {
        cin >> edge[i].from >> edge[i].to >> edge[i].len;
        --edge[i].from;
        --edge[i].to;
        adj[edge[i].from].insert(edge[i]);
        adj[edge[i].to].insert(Edge(edge[i].to, edge[i].from, edge[i].len));
    }
    for (int i=0; i<N; ++i) {
        real_leaf[i] = adj[i].size() == 1;
    }

    ll best = 0;
    for (int i=0; i<1<<(N-1); ++i) {
        for (int j=0; j<N; ++j) {
            adj[j].clear();
        }
        int edge_ct = 0;
        ll total = 0;
        for (int j=0; j<N-1; ++j) {
            if ((i >> j) & 1) {
                ll a = edge[j].from, b = edge[j].to;
                adj[a].insert(edge[j]);
                adj[b].emplace(b, a, edge[j].len);
                ++edge_ct;
                total += edge[j].len;
            }
        }
        if (edge_ct & 1) continue;

        if (works()) {
            best = max(best, total);
        }
    }

    cout << best << endl;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43