Submission #1248058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248058		firegirlwaterboy	Training (IOI07_training)	C++20	100 / 100	9 ms	4680 KiB

training

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1001, M = 5001, K = 10;

int n, m, sum;
pii par[N];
int anc[N][K + 1];
vector<int> paths[N];
int deg[N], order[N], depth[N], ptr;

struct Edge {
    int a, b, c, lca;
    bool operator<(const Edge &x) const { return order[lca] < order[x.lca]; }
};

vector<Edge> edges;

void dfs(int u, int p) {
    anc[u][0] = p;
    for (auto &v : paths[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1, par[v] = {u, 1 << (deg[u]++)};
        dfs(v, u);
    }
    order[u] = ptr;
    ptr++;
}

int ancestor(int a, int d) {
    for (int j = 0; j <= K; j++) {
        if (d & (1 << j)) a = anc[a][j];
    }
    return a;
}

int LCA(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    a = ancestor(a, depth[a] - depth[b]);
    if (a == b) return a;
    for (int j = K; j >= 0; j--) {
        if (anc[a][j] != anc[b][j]) a = anc[a][j], b = anc[b][j];
    }
    return anc[a][0];
}

int dp[N][1 << K];

void solve2() {
    for (auto &e : edges) {
        int a = e.a, b = e.b, cur = e.c, lca = e.lca;
        if (depth[a] % 2 != depth[b] % 2 && cur != 0) continue;
        int mask1, mask2;
        for (mask1 = 0; a != lca; tie(a, mask1) = par[a]) {
            cur += dp[a][mask1];
        }
        for (mask2 = 0; b != lca; tie(b, mask2) = par[b]) {
            cur += dp[b][mask2];
        }
        mask1 |= mask2;
        for (int mask = (1 << deg[lca]) - 1; mask >= 0; mask--) {
            if (mask & mask1) continue;
            dp[lca][mask] = max(dp[lca][mask], cur + dp[lca][mask | mask1]);
        }
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (!c) paths[a].push_back(b), paths[b].push_back(a);
        sum += c;
        edges.push_back({a, b, c, 0});
    }
    par[1] = {1, 0};
    dfs(1, 1);
    for (int j = 1; j <= K; j++) {
        for (int i = 1; i <= n; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
    for (auto &edge : edges) {
        if (depth[edge.a] % 2 != depth[edge.b] % 2 && edge.c != 0) continue;
        edge.lca = LCA(edge.a, edge.b);
    }
    sort(edges.begin(), edges.end());
    solve2();
    cout << sum - dp[1][0] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 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: 9 / 9
• Subtask 11: 9 / 9