Submission #1313512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313512		iamhereforfun	Training (IOI07_training)	C++20	30 / 100	5 ms	3040 KiB

training

// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e3 + 5;
const int M = 5e4 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e18 + 5;
const int B = 400;
const int MOD = 1e9;

int n, m, depth[N], binlift[LG][N], par[N], cid[N];
long long dp[N][N], sum, mx[N];
vector<int> adj[N];
vector<array<int, 3>> edges, query[N];

void dfs1(int c, int p)
{
    par[c] = p;
    int id = -1;
    for (int i : adj[c])
    {
        id++;
        if (i == p)
            continue;
        cid[i] = id;
        depth[i] = depth[c] + 1;
        binlift[0][i] = c;
        for (int x = 1; x < LG; x++)
        {
            binlift[x][i] = binlift[x - 1][binlift[x - 1][i]];
        }
        dfs1(i, c);
    }
}

int lca(int a, int b)
{
    if (depth[a] != depth[b])
    {
        if (depth[a] < depth[b])
            swap(a, b);
        for (int x = 0; x < LG; x++)
        {
            if ((depth[a] - depth[b]) >> x & 1)
            {
                a = binlift[x][a];
            }
        }
    }
    if (a == b)
        return a;
    for (int x = LG - 1; x >= 0; x--)
    {
        if (binlift[x][a] != binlift[x][b])
        {
            a = binlift[x][a];
            b = binlift[x][b];
        }
    }
    return binlift[0][a];
}

void dfs2(int c, int p)
{
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs2(i, c);
    }
    int s = adj[c].size();
    for (auto [a, b, v] : query[c])
    {
        long long cur = 0;
        if (a != c)
            cur += mx[a];
        if (b != c)
            cur += mx[b];
        // cout << cur << " " << a << " " << b << " " << c << " " << par[b] << " ";
        // cout << dp[par[b]][(((1 << adj[par[b]].size()) - 1) ^ (1 << cid[b]))] << "\n";
        while (par[a] != c && a != c)
        {
            cur += dp[par[a]][((1 << adj[par[a]].size()) - 1) ^ (1 << cid[a])];
            a = par[a];
        }
        while (par[b] != c && b != c)
        {
            cur += dp[par[b]][((1 << adj[par[b]].size()) - 1) ^ (1 << cid[b])];
            b = par[b];
        }
        int i1 = s, i2 = s;
        for (int id = 0; id < s; id++)
        {
            int &i = adj[c][id];
            if (i == a)
            {
                i1 = id;
            }
            if (i == b)
            {
                i2 = id;
            }
        }
        cur += v;
        for (int x = 0; x < (1 << s); x++)
        {
            mx[c] = max(dp[c][x], mx[c]);
        }
        // cout << mx[c] << " " << c << "dp\n";
        for (int x = (1 << s) - 1; x >= 0; x--)
        {
            if ((x >> i1 & 1) && i1 != s)
                continue;
            if ((x >> i2 & 1) && i2 != s)
                continue;
            int m = x;
            if (i1 != s)
                m |= (1 << i1);
            if (i2 != s)
                m |= (1 << i2);
            dp[c][m] = max(dp[c][m], dp[c][x] + cur);
        }
    }
    for (int x = 0; x < (1 << s); x++)
    {
        long long cur = dp[c][x];
        for (int y = 0; y < s; y++)
        {
            if (adj[c][y] == p)
                continue;
            if (x >> y & 1)
                continue;
            cur += mx[adj[c][y]];
        }
        mx[c] = max(mx[c], cur);
    }
    // cout << mx[c] << " " << c << "dp\n";
}

void solve()
{
    cin >> n >> m;
    for (int x = 0; x < m; x++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (c == 0)
        {
            adj[a].push_back(b);
            adj[b].push_back(a);
            // cout << a << " " << b << "\n";
        }
        else
        {
            sum += c;
            edges.push_back({a, b, c});
        }
    }
    dfs1(1, 0);
    for (auto &[a, b, c] : edges)
    {
        if ((depth[a] + depth[b]) % 2 == 0)
        {
            // cout << a << " " << b << " " << c << "\n";
            query[lca(a, b)].push_back({a, b, c});
        }
    }
    dfs2(1, 0);
    cout << sum - mx[1] << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9