Submission #1273614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273614		tphuocdz	Training (IOI07_training)	C++20	100 / 100	36 ms	8844 KiB

training

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
const int K = 10, N = (1 << (K)), INF = int(1e18);

int p[N], d[N], far[N][K + 1];
int dp[N][N];
vpi graf[N];          // adjacency: (neighbour, cost) cost==0 -> paved (tree) edge; cost>0 -> unpaved with weight
vtii k[N];            // for each LCA node: list of (a, b, val) representing even non-tree edges with TP passing through this node

void calc_far(int u){
    for(int i = 1; i <= K; i++){
        far[u][i] = far[far[u][i - 1]][i - 1];
    }
}

// dfs to set parent and depth using only paved edges (cost==0)
void dfs(int u, int v){
    d[u] = d[v] + 1;
    far[u][0] = v;
    calc_far(u);
    p[u] = v;
    for(auto [i, j] : graf[u]){
        if(j > 0 || i == v) continue; // only traverse tree (paved) edges
        dfs(i, u);
    }
}

// bring node a up to depth dep
void go_to_dep(int &a, int dep){
    if(d[a] == dep) return;
    int akt = 0;
    while(d[far[a][akt + 1]] > dep) akt++;
    a = far[a][akt];
    go_to_dep(a, dep);
}

int lca(int a, int b){
    if(d[a] > d[b]) swap(a, b);
    go_to_dep(b, d[a]);
    while(a != b){
        int akt = 0;
        while(far[a][akt + 1] != far[b][akt + 1]) akt++;
        a = far[a][akt];
        b = far[b][akt];
    }
    return a;
}

// remove odd non-tree edges and for even edges store them (k[l]) in the LCA
void fix(int u){
    vpi n;
    for(auto [i, j] : graf[u]){
        int l = lca(i, u);
        int dist = d[i] + d[u] - 2 * d[l];
        // keep paved edges; keep non-tree edges only if even (dist%2==0)
        if(dist % 2 == 0 || j == 0){
            n.pb({i, j});
            if(u < i && j > 0){
                // store even non-tree edge (u,i,j) to be processed at their LCA
                k[l].pb({u, i, j});
            }
        }
    }
    graf[u] = n;
}

// rec computes contribution of path from node u up to x, tracking which child-edge of parent is used
int rec(int u, int pp, int x, pi &dz){
    if(u == x){
        if(dz.ft == -1) dz.ft = pp;
        else dz.sc = pp;
        return 0;
    }
    int idx = N - 1, t = -1;
    for(auto [i,j] : graf[u]){
        t++;
        if(i == p[u] || j > 0) continue; // skip parent or non-tree edges
        if(i == pp) idx -= (1 << t);
    }
    return dp[u][idx] - dp[pp][N - 1] + rec(p[u], u, x, dz);
}

// main DP on tree
void solve(int u, int v){
    // solve for children first
    for(auto [i, j] : graf[u]){
        if(j > 0 || i == v) continue;
        solve(i, u);
    }
    // initialize dp[u] by summing full-subtree values of children
    for(int i = 0; i < N; i++){
        int t = -1;
        for(auto [x, j] : graf[u]){
            t++;
            if(x == v || j > 0) continue;
            dp[u][i] += dp[x][N - 1];
        }
    }
    // process even non-tree edges whose tree-path passes through u (stored in k[u])
    for(auto [a, b, val] : k[u]){
        pi dz = {-1, -1};
        int idx = 0, w = rec(a, -1, u, dz) + rec(b, -1, u, dz), t = -1, odj = 0;
        for(auto [i, j] : graf[u]){
            t++;
            if(i == v || j > 0) continue;
            if(i == dz.ft || i == dz.sc){
                idx += (1 << t);
                odj += dp[i][N - 1];
            }
        }
        // try to include this even non-tree edge (merge two child subtrees through u)
        for(int i = 0; i < N; i++){
            if((i & idx) == idx){
                dp[u][i] = max(dp[u][i], dp[u][i ^ idx] + val - odj + w);
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    int s = 0;
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graf[a].pb({b, c});
        graf[b].pb({a, c});
        s += c;
    }
    // root tree at 1: set parent of 1 to 1 and depth 0
    dfs(1, 1);
    for(int i = 1; i <= n; i++) fix(i);
    solve(1, 1);
    int ans = 0;
    for(int i = 0; i < N; i++) ans = max(ans, dp[1][i]);
    // minimal cost to block = total non-tree weights - max kept weight
    cout << s - ans << "\n";
    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