제출 #1131114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131114		krishnaar2305	Training (IOI07_training)	C++17	100 / 100	24 ms	21064 KiB

training

#include <bits/stdc++.h>
using namespace std;

// Constants
const int MAXN = 5001;
const int MAXK = 10;

// Global variables
vector<vector<int>> dp(MAXN, vector<int>(1 << MAXK, 0));
vector<int> in_time(MAXN, 0), out_time(MAXN, 0), lol(MAXN, 0), deg(MAXN, 0);
vector<pair<int, int>> pr(MAXN, {0, 0});
vector<vector<int>> adj(MAXN);
int timer = 0;

struct Road {
    int l, r, cost, lca;
    Road(int l, int r, int cost, int lca = 0) : l(l), r(r), cost(cost), lca(lca) {}
    bool operator<(const Road &other) const {
        return out_time[lca] < out_time[other.lca];
    }
};

void reset_globals() {
    fill(dp.begin(), dp.end(), vector<int>(1 << MAXK, 0));
    fill(in_time.begin(), in_time.end(), 0);
    fill(out_time.begin(), out_time.end(), 0);
    fill(lol.begin(), lol.end(), 0);
    fill(deg.begin(), deg.end(), 0);
    fill(pr.begin(), pr.end(), make_pair(0, 0));
    for (auto &v : adj) v.clear();
    timer = 0;
}

void dfs(int node, int parent) {
    ++timer;
    in_time[node] = timer;
    lol[node] = lol[parent] ^ 1;
    for (int neighbor : adj[node]) {
        if (neighbor != parent) {
            pr[neighbor] = {node, 1 << deg[node]};
            ++deg[node];
            dfs(neighbor, node);
        }
    }
    ++timer;
    out_time[node] = timer;
}

bool is_parent(int A, int B) {
    return in_time[A] <= in_time[B] && out_time[A] >= out_time[B];
}

int find_lca(int A, int B) {
    while (!is_parent(A, B)) {
        A = pr[A].first;
    }
    return A;
}

int solve(int n, int m, vector<tuple<int, int, int>> &road_data) {
    vector<Road> roads;
    int total_cost = 0;

    for (const auto &[a, b, c] : road_data) {
        total_cost += c;
        if (c == 0) {
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        roads.emplace_back(a, b, c);
    }

    dfs(1, 0);

    for (auto &road : roads) {
        road.lca = find_lca(road.l, road.r);
    }

    sort(roads.begin(), roads.end());

    for (const auto &road : roads) {
        if (road.cost && (lol[road.l] ^ lol[road.r]) == 1) {
            continue;
        }

        int cost_accumulated = road.cost;
        pair<int, int> A = {road.l, 0}, B = {road.r, 0};

        while (A.first != road.lca) {
            cost_accumulated += dp[A.first][A.second];
            A = pr[A.first];
        }

        while (B.first != road.lca) {
            cost_accumulated += dp[B.first][B.second];
            B = pr[B.first];
        }

        for (int mask = (1 << deg[road.lca]) - 1; mask >= 0; --mask) {
            if ((mask & (A.second | B.second)) == 0) {
                dp[road.lca][mask] = max(
                    dp[road.lca][mask],
                    cost_accumulated + dp[road.lca][mask | A.second | B.second]
                );
            }
        }
    }

    return (total_cost - dp[1][0]);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> road_data(m);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        road_data[i] = {a, b, c};
    }
    reset_globals();
    cout << solve(n, m, road_data) << endl;
    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