제출 #1313490

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313490		iamhereforfun	Training (IOI07_training)	C++20	10 / 100	5 ms	856 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 = 5e3 + 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];
long long dp[N], sum;
vector<int> adj[N];
vector<array<int, 3>> edges, query[N];

void dfs1(int c, int p)
{
    par[c] = p;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        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);
        dp[c] += dp[i];
    }
    int s = adj[c].size();
    long long mask[1 << s];
    memset(mask, 0, sizeof(mask));
    for (auto &[a, b, v] : query[c])
    {
        long long cur = 0;
        if (a != c)
            cur += dp[a];
        if (b != c)
            cur += dp[b];
        while (par[a] != c && a != c)
        {
            for (int i : adj[par[a]])
            {
                if (i != a && i != par[par[a]])
                {
                    cur += dp[i];
                }
            }
            if (par[a] == c)
                break;
            a = par[a];
        }
        while (par[b] != c && b != c)
        {
            for (int i : adj[par[b]])
            {
                if (i != b && i != par[par[b]])
                {
                    cur += dp[i];
                }
            }
            b = par[b];
        }
        int i1 = s, i2 = s, id = 0;
        for (int i : adj[c])
        {
            if (i == p)
            {
                id++;
                continue;
            }
            if (i == a)
            {
                i1 = id;
                id++;
                continue;
            }
            if (i == b)
            {
                i2 = id;
                id++;
                continue;
            }
            id++;
            cur += dp[i];
        }
        cur += v;
        for (int x = 0; x < (1 << s); 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);
            mask[m] = max(mask[m], mask[x] + cur);
        }
    }
    for (int id = 0; id < s; id++)
    {
        int &i = adj[c][id];
        if (i == p)
            continue;
        for (int x = 0; x < (1 << s); x++)
        {
            if (x >> id & 1)
                continue;
            mask[x] += dp[i];
        }
    }
    for (int x = 0; x < (1 << s); x++)
    {
        dp[c] = max(mask[x], dp[c]);
    }
    // cout << dp[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);
        }
        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)
        {
            query[lca(a, b)].push_back({a, b, c});
        }
    }
    dfs2(1, 0);
    cout << sum - dp[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: 0 / 10
• Subtask 3: 0 / 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