Submission #799183

#	Time	Username	Problem	Language	Result	Execution time	Memory
799183		adrilen	Training (IOI07_training)	C++17	30 / 100	8 ms	4636 KiB

training

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr int maxn = 1e3 + 5, maxm = 5e3;

int dp[maxn][1 << 10] = { 0 };

int parent[maxn] = { 0 };
basic_string <int> chld[maxn];


arrr edges[maxm];
basic_string<int>adj[maxn];
arr order[maxn] = { 0 };
int order_to_pos[maxn * 2 + 5] = { 0 };
int depth[maxn] = { 0 };

int t = 0;
void fnd_tree(int p, int par, int dep)
{
    depth[p] = dep;
    // order_to_pos[t] = p;
    order[p][0] = t++;

    for (int i : adj[p])
    {
        if (i == par) continue;

        chld[p].push_back(i);
        parent[i] = p;
        fnd_tree(i, p, dep + 1);
    }
    order_to_pos[t] = p;
    order[p][1] = t++;
}


arr calc_upwards(int p, int fin, int fr)
{
    if (p == fin && p == fr) return {0, (int)chld[p].size()};

    int ind = 0;
    for (int i : chld[p])
    {
        if (i == fr) break;
        ind++;
    }
    if (p == fin) return {0, ind};

    arr r = calc_upwards(parent[p], fin, p);
    r[0] = (p == fr ? dp[p][(1 << (chld[p].size())) - 1] : dp[p][(1 << (chld[p].size())) - (1 << ind) - 1]);
    return r;
}


priority_queue<arrr, vector<arrr>, greater<arrr>> forw, backw;

void dfs(int p)
{
    vector<arrr> new_edges;

    for (int i : chld[p])
    {
        while (!backw.empty() && backw.top()[0] <= order[p][1])
        {
            new_edges.emplace_back(backw.top());
            backw.pop();
        }
        dfs(i);
    }

    while (!backw.empty() && backw.top()[0] <= order[p][1])
    {
        new_edges.emplace_back(backw.top());
        backw.pop();
    }


    // Finding max without using this node
    for (int i: chld[p]) // Going through each child and finding their best
    {
        dp[p][0] += dp[i][(1 << (chld[i].size())) - 1];
    }

    int s = chld[p].size();

    vector<vector<int>>opt_edges(s + 1, vector<int>(s + 1));

    auto it = new_edges.begin();
    arr l, r;
    arrr a;

    while (it != new_edges.end())
    {   
        a = *it++;

        a[0] = order_to_pos[a[0]];
        
        l = calc_upwards(a[0], p, a[0]),
        r = calc_upwards(a[1], p, a[1]);


        if (l[1] > r[1]) swap(l, r);

        opt_edges[l[1]][r[1]] = max(
            opt_edges[l[1]][r[1]], 
            l[0] + r[0] + a[2] - dp[p][0]
        );
    }


    // for (int i = 0; i <=  s; i++)
    // {
    //     for (int j = 0; j <= s; j++)
    //     {
    //         cout << opt_edges[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    // Bitset dp
    for (int i = 1; i < (1 << s); i++)
    {
        for (int j = 0; j < s; j++)
        {
            if ((i & (1 << j)) == 0) continue;

            dp[p][i] = max(dp[p][i], dp[p][i - (1 << j)] + opt_edges[j][s]);

            for (int k = j + 1; k < s; k++)
            {
                if ((i & (1 << k)) == 0) continue;
                dp[p][i] = max(dp[p][i], dp[p][i - (1 << j) - (1 << k)] + opt_edges[j][k]);
            }
        }
        // if (__builtin_popcount(i) == 1) cout << "\n";
        // cout << i << " " << dp[p][i] << "\t";
    }
    // cout << "\n";

    // Return new edges
    while (!forw.empty() && forw.top()[0] == order[p][1])
    {
        a = forw.top();
        forw.pop();

        a[0] = order_to_pos[a[0]];
        swap(a[0], a[1]);
        a[0] = order[a[0]][1];

        backw.push(a);
    }
}   


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
    }
    
    sort(edges, edges + m, [](const auto &l, const auto &r) {
        return l[2] < r[2];
    });


    for (int i = 0; i < n - 1; i++)
    {
        adj[edges[i][0]].push_back(edges[i][1]);
        adj[edges[i][1]].push_back(edges[i][0]);
    }

    fnd_tree(1, 0, 0);

    int output = 0;

    for (int i = n - 1; i < m; i++)
    {
        output += edges[i][2];

        if ((depth[edges[i][0]] ^ depth[edges[i][1]]) & 1) {
            continue;
        }

        if (order[edges[i][0]][1] > order[edges[i][1]][1]) swap(edges[i][0], edges[i][1]);
        edges[i][0] = order[edges[i][0]][1];
        forw.push(edges[i]);
    }
    

    dfs(1);

    cout << output - dp[1][(1 << (chld[1].size())) - 1] << "\n";

    // for (int i = 1; i <= n; i++) cout << dp[i][(1 << (chld[i].size())) - 1] << " ";
    // cout << "\n";
    // cout << output << "\n";
    assert(forw.empty());
    assert(backw.empty());
}   

• 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