Submission #955895

#	Time	Username	Problem	Language	Result	Execution time	Memory
955895		TimAni	Training (IOI07_training)	C++17	100 / 100	13 ms	4952 KiB

training

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

using namespace std;
using ll = long long;

const int N = 1000;
const int K = 10;

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;
    int ptr = 0;
public:
    LCA(const vector<vector<int>>& tree){
        int n = tree.size();
        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, 0, dfs);
        for(int j = 1; j < K; 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 - 1; 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];
    }
    void print(){
	    for(int i = 0; i < ptr; i++){
		    cout << dep[i] << ' ';
	    }
    }
};
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, 4>> 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);
        }
        edges.push_back({u, v, c, 0});
    }

    LCA TREE(tree);
    edges.erase(remove_if(edges.begin(), edges.end(), [&](const array<int, 4>& a) {
        return (TREE.dist(a[0], a[1]) % 2 != 0) && a[2];
    }), edges.end());
    
    for(auto &[a, b, c, d] : edges){
        d = TREE.lca(a, b);
    }

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