Submission #1272317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272317		olizarowskib	Training (IOI07_training)	C++20	100 / 100	37 ms	8840 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>
#define vtiii vector<tiii>

const int K = 10, N = (1 << (K)), MOD = 1e9 + 7, INF = int(1e18);

int p[N], d[N], far[N][K + 1];
int dp[N][N];
vpi graf[N];
vtii k[N];
void calc_far(int u){
    for(int i = 1; i <= K; i++){
        far[u][i] = far[far[u][i - 1]][i - 1];
    }
}

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;
        dfs(i, u);
    }
}

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;
}

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];
        if(dist % 2 == 0 || j == 0){
            n.pb({i, j});
            if(u < i && j > 0){
                k[l].pb({u, i, j});
            }
        }
    }
    graf[u] = n;
}

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;
        if(i == pp) idx -= (1 << t);
    }
    return dp[u][idx] - dp[pp][N - 1] + rec(p[u], u, x, dz);
}

void solve(int u, int v){
    for(auto [i, j] : graf[u]){
        if(j > 0 || i == v) continue;
        solve(i, u);
    }
    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];
        }
    }
    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];
            }
        }
        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;
    }
    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]);
    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