oj.uz

Submission #955896

# Submission time Handle Problem Language Result Execution time Memory
955896 2024-03-31T16:23:24 Z TimAni Training (IOI07_training) C++17
100 / 100
 13 ms 4760 KB 
//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;
public:
    LCA(const vector<vector<int>>& tree){
        int n = tree.size();
        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, 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];
    }
};
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]);
    });
    
    vector<vector<int>> dp(n, vector<int>(1<<K));
    for(auto &[a, b, w, lca] : edges){
        int mask1 = 0, mask2 = 0;
        for(; a != lca; tie(a, mask1) = TREE.parent(a)) w += dp[a][mask1];
        for(; 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 600 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4696 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct
3 Correct 4 ms 2396 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4696 KB Output is correct
2 Correct 8 ms 4700 KB Output is correct
3 Correct 9 ms 4624 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2392 KB Output is correct
2 Correct 4 ms 2652 KB Output is correct
3 Correct 11 ms 4760 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4700 KB Output is correct
2 Correct 13 ms 4760 KB Output is correct
3 Correct 10 ms 4700 KB Output is correct
4 Correct 10 ms 4700 KB Output is correct