oj.uz

Submission #799149

# Submission time Handle Problem Language Result Execution time Memory
799149 2023-07-31T10:13:35 Z adrilen Training (IOI07_training) C++17
30 / 100
 7 ms 4692 KB 
#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]
        );
    }


    // Bitset dp
    for (int i = 0; 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++)
            {
                dp[p][i] = max(dp[p][i], dp[p][i - (1 << j) - (1 << k)] + opt_edges[j][k]);
            }
        }
    }

    // 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";

    assert(forw.empty());
    assert(backw.empty());
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 532 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4632 KB Output is correct
2 Correct 6 ms 4692 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2132 KB Output isn't correct
2 Halted 0 ms 0 KB -