Submission #610550

#	Time	Username	Problem	Language	Result	Execution time	Memory
610550		dooompy	Training (IOI07_training)	C++17	72 / 100	1089 ms	2396 KiB

training

#include <bits/stdc++.h>

using namespace std;

struct edge {
    int a, b, c, lca;
};

vector<edge> edges, fe;
int total = 0;
vector<int> adj[1005];

int tin[1005], timer = 1;
int jmp[1005][12], depth[1005];
int col[1005];
pair<int, int> par[1005];
int deg[1005];
int dp[1005][1 << 11];

void dfs(int node) {
    tin[node] = timer++;

    for (int i = 1; i < 12; i++) jmp[node][i] = jmp[jmp[node][i-1]][i-i];

    for (auto nxt : adj[node]) {
        if (tin[nxt]) continue;
        if (col[node] == 1) {
            col[nxt] = 2;
        } else col[nxt] = 1;
        par[nxt] = {node, (1 << deg[node]++)};
        depth[nxt] = depth[node] + 1;
        jmp[nxt][0] = node;
        dfs(nxt);
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);

    for (int i = 11; i >= 0; i--) {
        if (depth[jmp[b][i]] >= depth[a]) b = jmp[b][i];
    }

    if (a == b) return a;

    for (int i = 11; i >= 0; i--) {
        if (jmp[a][i] != jmp[b][i]) {
            a = jmp[a][i]; b = jmp[b][i];
        }
    }

    return jmp[a][0];
}

int main() {
    int n, m; cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        total += c;
        if (c == 0) {
            adj[a].push_back(b); adj[b].push_back(a);
        }

        edges.push_back({a, b, c});
    }

    col[1] = 1;
    jmp[1][0] = 1;
    depth[1] = 1;

    dfs(1);

    for (auto e: edges) {
        if (col[e.a] == col[e.b]) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
        else if (e.c == 0) fe.push_back({e.a, e.b, e.c, lca(e.a, e.b)});
    }

    sort(fe.begin(), fe.end(), [&](edge a, edge b) {
        return tin[a.lca] > tin[b.lca];
    });

    for (auto e : fe) {
        int tot = e.c;
        int finalmask = 0;
        int mask = 0;
        for (int i = e.a; i != e.lca; mask = par[i].second, i = par[i].first) {
            tot += dp[i][mask];
        }
        finalmask |= mask;
        mask = 0;
        for (int i = e.b; i != e.lca;mask = par[i].second, i = par[i].first) {
            tot += dp[i][mask];
        }
        finalmask |= mask;

        for (int mk = (1 << deg[e.lca]) - 1; mk >= 0 ; mk--) {
            if (mk & finalmask) continue;
            dp[e.lca][mk] = max(dp[e.lca][mk], dp[e.lca][mk | finalmask] + tot);
        }

    }
    cout << total - dp[1][0];
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 7 / 7
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9