Submission #685678

#	Time	Username	Problem	Language	Result	Execution time	Memory
685678		finn__	Training (IOI07_training)	C++17	20 / 100	11 ms	1492 KiB

training

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    uint64_t u, v, w;
};

vector<vector<uint64_t>> g, anc;
vector<uint64_t> height, ind;
vector<vector<Edge>> unpaved;
vector<vector<uint64_t>> dp;

uint64_t lift(uint64_t u, uint64_t h)
{
    uint64_t z = 0;
    while (h)
    {
        if (h & 1)
        {
            assert(z < anc[u].size());
            u = anc[u][z];
        }
        h >>= 1;
        z++;
    }
    return u;
}

uint64_t lca(uint64_t u, uint64_t v)
{
    assert(u < g.size() && v < g.size());
    if (height[u] < height[v])
        swap(u, v);
    u = lift(u, height[u] - height[v]);
    if (u == v)
        return u;

    for (uint64_t i = anc[u].size() - 1; i < anc[u].size(); i--)
    {
        if (anc[u][i] != anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    }

    return anc[u][0];
}

void traverse(uint64_t u, vector<uint64_t> &path, uint64_t p = -1, uint64_t h = 0)
{
    for (uint64_t i = 1; i <= path.size(); i <<= 1ULL)
        anc[u].push_back(path[path.size() - i]);
    height[u] = h;
    path.push_back(u);

    for (uint64_t const &v : g[u])
        if (v != p)
            traverse(v, path, u, h + 1);

    path.pop_back();
}

void calc_dp(uint64_t u)
{
    for (uint64_t const &v : g[u])
    {
        calc_dp(v);
    }

    dp[u] = vector<uint64_t>(1ULL << g[u].size());
    // Case 1. Just delete the root and add up subtree values.
    for (uint64_t z = 0; z < (1ULL << g[u].size()); z++)
    {
        dp[u][z] = 0;
        for (uint64_t i = 0; i < g[u].size(); i++)
        {
            if (!(z & (1ULL << i)))
            {
                dp[u][z] += dp[g[u][i]][0];
            }
        }
    }

    for (uint64_t i = 0; i < g[u].size(); i++)
    {
        ind[g[u][i]] = i;
    }

    // Case 2: Take exactly one unpaved road whose tree path contains u.
    for (auto const &[a, b, w] : unpaved[u])
    {
        // Stores just the value obtained from the two used subtrees.
        uint64_t x = 0;
        if (a != u)
        {
            x += dp[a][0];
            uint64_t r = a, s = anc[a][0];
            while (s != u)
            {
                // assert(dp[s].size() == 1ULL << g[s].size());
                x += dp[s][1ULL << ind[r]];
                r = s;
                s = anc[s][0];
            }
        }
        if (b != u)
        {
            x += dp[b][0];
            uint64_t r = b, s = anc[b][0];
            while (s != u)
            {
                x += dp[s][1ULL << ind[r]];
                r = s;
                s = anc[s][0];
            }
        }

        uint64_t p = UINT_MAX, q = UINT_MAX;

        if (a != u)
            p = ind[lift(a, height[a] - height[u] - 1)];
        if (b != u)
            q = ind[lift(b, height[b] - height[u] - 1)];

        for (uint64_t z = 0; z < (1ULL << g[u].size()); z++)
        {
            if ((a != u && (z & (1ULL << p))) || (b != u && (z & (1ULL << q))))
                continue;

            uint64_t y = 0;
            // Sum all children not on an edge path and not ruled out.
            for (uint64_t i = 0; i < g[u].size(); i++)
            {
                if (!(z & (1ULL << i)) && i != p && i != q)
                {
                    y += dp[g[u][i]][0];
                }
            }
            dp[u][z] = max(dp[u][z], x + y + w);
        }
    }

    assert(dp[u].size() == (1ULL << g[u].size()));
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    size_t n, m;
    cin >> n >> m;

    g = vector<vector<uint64_t>>(n);
    vector<Edge> unpaved_edges;
    uint64_t total_cost = 0;

    for (size_t i = 0; i < m; i++)
    {
        uint64_t u, v, w;
        cin >> u >> v >> w;
        total_cost += w;

        if (!w)
        {
            g[u - 1].push_back(v - 1);
            g[v - 1].push_back(u - 1);
        }
        else
        {
            unpaved_edges.push_back({u - 1, v - 1, w});
        }
    }

    height = vector<uint64_t>(n);
    anc = vector<vector<uint64_t>>(n);
    vector<uint64_t> path;
    traverse(0, path);

    for (uint64_t u = 0; u < n; u++)
    {
        for (auto it = g[u].begin(); it != g[u].end(); it++)
        {
            if (!anc[u].empty() && *it == anc[u][0])
            {
                g[u].erase(it);
                break;
            }
        }
    }

    unpaved = vector<vector<Edge>>(n);
    for (auto const &[u, v, w] : unpaved_edges)
    {
        if (!((height[u] + height[v]) & 1))
        {
            assert(lca(u, v) < n);
            unpaved[lca(u, v)].push_back({u, v, w});
        }
    }

    dp = vector<vector<uint64_t>>(n);
    ind = vector<uint64_t>(n);
    calc_dp(0);

    cout << total_cost - dp[0][0] << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 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