Submission #955870

#	Time	Username	Problem	Language	Result	Execution time	Memory
955870		TimAni	Training (IOI07_training)	C++17	0 / 100	18 ms	8796 KiB

training

//start-time: 2024-03-31 16:15:50
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1001;
const int K = 11;

class LCA {
private:
    static vector<vector<int>> table;
    static vector<array<int, 2>> par;
    static vector<int> order;
    static vector<int> dep;
    static vector<int> deg;
public:
    LCA(const vector<vector<int>>& tree){
        int n = tree.size();
        int log = ceil(log2(n));
        int ptr = 0;
        auto dfs = [&](int u, int p, auto&& dfs) -> void {
            for(auto v : tree[u]){
                if(v != p) {
                    table[v][0] = u;
                    dep[v] = dep[u] + 1;
                    par[v] = {u, 1<<(deg[u]++)};
                    dfs(v, u, dfs);
                }
            }
            order[u] = ptr++;
        };
        dfs(0, -1, dfs);
        for(int j = 1; j < log; j++)
            for(int i = 0; i < n; i++)
                table[i][j] = table[table[i][j - 1]][j - 1];
    }
    tuple<int, int> parent(int u){
        return make_tuple(par[u][0], par[u][1]);
    }
    int jump(int u, int dist) {
        for(int i = 0; i < K; i++)
            if(dist & (1<<i))
                u = table[u][i];
        return u;
    }
    int lca(int u, int v){
        if(dep[u] > dep[v]) swap(u, v);
        v = jump(v, dep[v] - dep[u]);
        if(v == u) return v;
        for(int j = K; j >= 0; j--){
            if(table[u][j] != table[v][j]){
                u = table[u][j];
                v = table[v][j];
            }
        }
        return table[u][0];
    }
    int dist(int u, int v){
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int getOrder(int u){
        return order[u];
    }
};
vector<vector<int>> LCA::table = vector<vector<int>>(N, vector<int>(K));
vector<array<int, 2>> LCA::par = vector<array<int, 2>>(N);
vector<int> LCA::order = vector<int>(N);
vector<int> LCA::dep = vector<int>(N);
vector<int> LCA::deg = vector<int>(N);

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> tree(n);
    vector<array<int, 3>> edges;
    ll sum = 0;
    for(int i = 0; i < m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        u--; v--;
        sum += c;
        if(c == 0){
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        else edges.push_back({u, v, c});
    }

    LCA TREE(tree);
    edges.erase(remove_if(edges.begin(), edges.end(), [&](const array<int, 3>& a) {
        return TREE.dist(a[0], a[1]) % 2 != 0;
    }), edges.end());
    

    sort(edges.begin(), edges.end(), [&](const array<int, 3>& a, const array<int, 3>& b){
        return TREE.getOrder(TREE.lca(a[0], a[1])) < TREE.getOrder(TREE.lca(b[0], b[1]));
    });
    
    int mask1, mask2;
    vector<vector<int>> dp(n, vector<int>(1<<K));
    for(auto [a, b, w] : edges){
        int lca = TREE.lca(a, b);

        for(mask1 = 0; a != lca; tie(a, mask1) = TREE.parent(a)) w += dp[a][mask1];
        for(mask2 = 0; b != lca; tie(b, mask2) = TREE.parent(b)) w += dp[b][mask2];

        mask1 |= mask2;
        for(int mask = 0; mask < 1<<K; mask++){
            if(mask & mask1) continue;
            dp[lca][mask] = max(dp[lca][mask], w + dp[lca][mask | mask1]);
        }
    }
    cout << sum - dp[0][0];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    //cin >> T;
    while(T--) solve();
    return 0;
}

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