oj.uz

Submission #996808

# Submission time Handle Problem Language Result Execution time Memory
996808 2024-06-11T09:21:17 Z Ghetto Training (IOI07_training) C++17
100 / 100
 207 ms 166484 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e3 + 5, MAX_M = 5e3 + 5;

int n, m;
vector<int> adj[MAX_N];
struct Edge {
    int u, v, val;
};
Edge edge[MAX_M];

int n_inds, ind[MAX_N], f_ind[MAX_N];
int depth[MAX_N];
int anc[MAX_N][20];
vector<int> children[MAX_N];
int child_ind[MAX_N];
void dfs1(int u = 1, int par = -1) {
    n_inds++, ind[u] = n_inds;
    for (int v : adj[u]) {
        if (v == par) continue;
        anc[v][0] = u, depth[v] = depth[u] + 1;
        children[u].push_back(v), child_ind[v] = children[u].size() - 1;
        dfs1(v, u);
    }
    f_ind[u] = n_inds;
}
void precomp1() {
    dfs1();
    for (int i = 1; i <= 19; i++)
        for (int u = 1; u <= n; u++)
            anc[u][i] = anc[anc[u][i - 1]][i - 1];
}

int lca(int u, int v) {
    auto is_anc = [](int u, int v) { return ind[u] <= ind[v] && ind[v] <= f_ind[u]; };
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    
    for (int i = 19; i >= 0; i--) 
        if (anc[u][i] != 0 && !is_anc(anc[u][i], v))
            u = anc[u][i];
    u = anc[u][0];
    return u;
}
int val_sum;
vector<int> paths[MAX_N], path[MAX_M], path_children[MAX_M][MAX_N];
void precomp2() { 
    for (int i = 1; i <= m; i++) {
        val_sum += edge[i].val;
        int w = lca(edge[i].u, edge[i].v);
        int len = depth[edge[i].u] + depth[edge[i].v] - 2 * depth[w] + 1;
        // cout << edge[i].u << " " << edge[i].v << ": " << w << " " << len << endl;
        if (len % 2 == 0) continue;
        
        paths[w].push_back(i);
        path[i].push_back(w);
        auto climb = [](int u, int i, int w) {
            while (true) {
                if (u == w) break;
                path[i].push_back(u);
                path_children[i][anc[u][0]].push_back(u);
                u = anc[u][0];
            }
        };
        climb(edge[i].u, i, w), climb(edge[i].v, i, w);
        // cout << i << ": ";
        // for (int u : path[i]) cout << u << " ";
        // cout << endl;
    }
}

int dp[MAX_N][1 << 10];
int trans[MAX_M];
void dfs2(int u = 1) {
    for (int v : children[u]) dfs2(v);

    for (int i : paths[u]) {
        trans[i] = edge[i].val;
        for (int v : path[i]) {
            if (v == u) continue;
            int mask = (1 << children[v].size()) - 1;
            for (int w : path_children[i][v]) mask ^= (1 << child_ind[w]);
            trans[i] += dp[v][mask];
        }
    }

    for (int mask = 0; mask <= (1 << children[u].size()) - 1; mask++) {
        // Case where we don't take any paths
        for (int i = 0; i <= (int) children[u].size() - 1; i++) {
            if (!(mask & (1 << i))) continue;
            int v = children[u][i];
            dp[u][mask] += dp[v][(1 << children[v].size()) - 1];
        }

        for (int i : paths[u]) {
            bool halt = false;
            for (int v : path_children[i][u])
                if (!(mask & (1 << child_ind[v]))) halt = true;
            if (halt) continue;

            int new_mask = mask;
            for (int v : path_children[i][u]) new_mask ^= (1 << child_ind[v]);
            dp[u][mask] = max(dp[u][mask], dp[u][new_mask] + trans[i]);
        }
        // cout << u << " " << mask << ": " << dp[u][mask] << endl;
    }
}

int main() {
    // freopen("train.in", "r", stdin);
    cin >> n >> m;
    int new_m = 0;
    for (int i = 1; i <= m; i++) {
        int u, v, val; cin >> u >> v >> val;
        if (val == 0) adj[u].push_back(v), adj[v].push_back(u);
        else new_m++, edge[new_m] = {u, v, val}; 
    }
    m = new_m;
    
    precomp1();
    precomp2();
    dfs2();

    int ans = val_sum - dp[1][(1 << children[1].size()) - 1];
    cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 122716 KB Output is correct
2 Correct 21 ms 122716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 135252 KB Output is correct
2 Correct 70 ms 136528 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 120588 KB Output is correct
2 Correct 20 ms 120412 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 120668 KB Output is correct
2 Correct 20 ms 120588 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 121176 KB Output is correct
2 Correct 23 ms 120924 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 121692 KB Output is correct
2 Correct 25 ms 123224 KB Output is correct
3 Correct 36 ms 124036 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 125276 KB Output is correct
2 Correct 34 ms 121940 KB Output is correct
3 Correct 38 ms 122456 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 121180 KB Output is correct
2 Correct 44 ms 125520 KB Output is correct
3 Correct 100 ms 166484 KB Output is correct
4 Correct 50 ms 128852 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 136016 KB Output is correct
2 Correct 207 ms 166424 KB Output is correct
3 Correct 98 ms 138064 KB Output is correct
4 Correct 43 ms 122192 KB Output is correct