Submission #845602

#	Time	Username	Problem	Language	Result	Execution time	Memory
845602		tibinyte	Closing Time (IOI23_closing)	C++17	51 / 100	1133 ms	2097152 KiB

closing

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 1;
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w)
{
    x++;
    y++;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < n - 1; ++i)
    {
        u[i]++;
        v[i]++;
        g[u[i]].push_back({v[i], w[i]});
        g[v[i]].push_back({u[i], w[i]});
    }
    vector<vector<ll>> cost(n + 1, vector<ll>(2));
    function<void(int, int, int)> compute_cost = [&](int node, int parent, int qui)
    {
        for (auto i : g[node])
        {
            if (i.first != parent)
            {
                cost[i.first][qui] = cost[node][qui] + i.second;
                compute_cost(i.first, node, qui);
            }
        }
    };
    compute_cost(x, 0, 0);
    compute_cost(y, 0, 1);

    function<int()> greedy = [&]()
    {
        set<tuple<ll, int, int>> accesibile;
        vector<vector<int>> viz(n + 1, vector<int>(2));
        accesibile.insert({0, x, 0});
        accesibile.insert({0, y, 1});
        int ans = 0;
        ll left = k;
        while (!accesibile.empty())
        {
            int adam, qui, byqui;
            tie(adam, qui, byqui) = *accesibile.begin();
            accesibile.erase(accesibile.begin());
            if (adam > left)
            {
                break;
            }
            left -= adam;
            ans++;
            viz[qui][byqui] = true;
            for (auto i : g[qui])
            {
                if (!viz[i.first][byqui])
                {
                    accesibile.insert({cost[i.first][byqui], i.first, byqui});
                }
            }
        }
        return ans;
    };

    function<int(int)> solve_root = [&](int root)
    {
        vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + n + 1, vector<ll>(3, inf)));
        vector<bool> important(n + 1);
        vector<int> sz(n + 1);
        function<void(int, int)> dfs_important = [&](int node, int parent)
        {
            if (node == x || node == y)
            {
                important[node] = true;
            }
            for (auto i : g[node])
            {
                if (i.first != parent)
                {
                    dfs_important(i.first, node);
                }
            }
            for (auto i : g[node])
            {
                if (i.first != parent)
                {
                    important[node] = important[node] || important[i.first];
                }
            }
        };
        dfs_important(root, 0);
        vector<ll> merged(n + n + 1, inf);
        function<void(int, int)> dfs = [&](int node, int parent)
        {
            dp[node][1][0] = cost[node][0];
            dp[node][1][1] = cost[node][1];
            dp[node][2][2] = max(cost[node][0], cost[node][1]);
            sz[node] = 1;

            if (node == x)
            {
                dp[node][1][1] = inf;
            }
            if (node == y)
            {
                dp[node][1][0] = inf;
            }
            for (auto i : g[node])
            {
                if (i.first != parent)
                {
                    dfs(i.first, node);
                    int maxleft = sz[node] + sz[node];
                    int maxright = sz[i.first] + sz[i.first];
                    for (int i = 0; i <= maxleft + maxright; ++i)
                    {
                        merged[i] = inf;
                    }
                    for (int color = 0; color <= 2; ++color)
                    {
                        for (int color2 = 0; color2 <= 2; ++color2)
                        {
                            if (color != color2 && color != 2)
                            {
                                continue;
                            }
                            for (int cntleft = 1; cntleft <= maxleft; ++cntleft)
                            {
                                for (int cntright = 1; cntright <= maxright; ++cntright)
                                {
                                    merged[cntleft + cntright] = min(merged[cntleft + cntright], dp[node][cntleft][color] + dp[i.first][cntright][color2]);
                                }
                            }
                        }
                        for (int cnt = 1; cnt <= maxleft + maxright; ++cnt)
                        {
                            if (important[i.first])
                            {
                                dp[node][cnt][color] = merged[cnt];
                            }
                            else
                            {
                                dp[node][cnt][color] = min(dp[node][cnt][color], merged[cnt]);
                            }
                        }
                    }
                    sz[node] += sz[i.first];
                }
            }
        };
        dfs(root, 0);
        for (int i = n + n; i >= 1; --i)
        {
            if (dp[root][i][2] <= k)
            {
                return i;
            }
        }
        return 0;
    };
    int ans = greedy();
    vector<int> lying;
    function<void(int, int, vector<int>)> find_nodes = [&](int node, int parent, vector<int> curent)
    {
        curent.push_back(node);
        if (node == y)
        {
            lying = curent;
        }
        for (auto i : g[node])
        {
            if (i.first != parent)
            {
                find_nodes(i.first, node, curent);
            }
        }
        curent.pop_back();
    };
    find_nodes(x, 0, {});
    sort(lying.begin(), lying.end(), [&](int x, int y)
         { return abs(cost[x][0] - cost[x][1]) < abs(cost[y][0] - cost[y][1]); });
    ans = max(ans, solve_root(lying[0]));
    return ans;
}

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