Submission #1167017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167017		nh0902	Training (IOI07_training)	C++20	100 / 100	9 ms	4680 KiB

training

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second

const int N = 1005;

const int inf = 1e15;

const long long mod = 998244353;

const long long p2 = 31;

int n, m;

vector<int> g[N];

int d[N], cnt[N], pos[N], pa[N][12];

struct Bridge {
    int a, b, w;
};

vector<Bridge> store[N];

vector<pair<pair<int, int>, int>> E;

int dp[N][1 << 11];

void dfs(int u, int p, int cur_d) {
    pa[u][0] = p;
    d[u] = cur_d;
    for (int v : g[u]) if (v != p) {
        pos[v] = cnt[u];
        cnt[u] ++;
        dfs(v, u, cur_d + 1);
    }
}

void lca_process(int a, int b, int w) {
    if (d[a] % 2 != d[b] % 2) return;
    if (d[a] > d[b]) swap(a, b);
    int u = a, v = b;
    int k = d[v] - d[u];
    for (int i = 11; i >= 0; i --) {
        if ((k >> i) & 1) v = pa[v][i];
    }

    if (u == v) {
        store[u].push_back({b, b, w});
        return;
    }

    for (int i = 11; i >= 0; i --) {
        if (pa[u][i] != pa[v][i]) {
            u = pa[u][i];
            v = pa[v][i];
        }
    }

    store[pa[u][0]].push_back({a, b, w});
}

void prep() {
    dfs(1, 1, 0);

    for (int k = 1; k < 12; k ++) {
        for (int i = 1; i <= n; i ++) {
            pa[i][k] = pa[pa[i][k - 1]][k - 1];
        }
    }

    for (auto e : E) {
        lca_process(e.fi.fi, e.fi.se, e.se);
    }

}

void DFS(int u, int p) {

    int best[cnt[u]][cnt[u]];

    for (int i = 0; i < cnt[u]; i ++) {
        for (int j = 0; j < cnt[u]; j ++) {
            best[i][j] = 0;
        }
    }

    for (int v : g[u]) if (v != p) {
        DFS(v, u);
        best[pos[v]][pos[v]] = dp[v][(1 << cnt[v]) - 1];
    }


    for (Bridge br : store[u]) {
        //cout << u << " : " << br.a << " - " << br.b << " , " << br.w << "\n";
        int a = br.a;
        int sum = 0;

        sum = dp[a][(1 << cnt[a]) - 1];
        while (true) {
            int p = pa[a][0];
            sum += dp[p][(1 << cnt[p]) - 1 - (1 << pos[a])];
            if (p == u) {
                break;
            }
            a = p;
        }

        if (br.a == br.b) {
            best[pos[a]][pos[a]] = max(best[pos[a]][pos[a]], sum + br.w);
        }

        else {
            int b = br.b;
            sum += dp[b][(1 << cnt[b]) - 1];
            while (true) {
                int p = pa[b][0];
                sum += dp[p][(1 << cnt[p]) - 1 - (1 << pos[b])];
                if (p == u) break;
                b = p;
            }

            best[pos[b]][pos[a]] = best[pos[a]][pos[b]] = max(best[pos[a]][pos[b]], sum + br.w);
        }
    }


    for (int mask = 1; mask < (1 << cnt[u]); mask ++) {
        int i = cnt[u] - 1;
        while (((mask >> i) & 1) == 0) i --;
        for (int t = 0; t <= i; t ++) {
            if ((mask >> t) & 1) {
                dp[u][mask] = max(dp[u][mask], dp[u][mask - (1 << t)] + best[t][t]);
                dp[u][mask] = max(dp[u][mask], dp[u][mask - (1 << t) - (1 << i)] + best[i][t]);
            }
        }
    }

    //cout << u << " " << dp[u][(1 << cnt[u]) - 1] << "\n";

}



signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

    int sum = 0;
    int a, b, c;
    for (int i = 1; i <= m; i ++) {
        cin >> a >> b >> c;
        if (c == 0) {
            g[a].push_back(b);
            g[b].push_back(a);
        } else {
            E.push_back({{a, b}, c});
            sum += c;
        }
    }

    prep();
    DFS(1, 1);

    cout << sum - dp[1][(1 << cnt[1]) - 1];

    return 0;
}

Compilation message (stderr)

training.cpp:11:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   11 | const int inf = 1e15;
      |                 ^~~~

• 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