답안 #845620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
845620	2023-09-06T14:31:53 Z	tibinyte	봉쇄 시간 (IOI23_closing)	C++17	9 / 100	933 ms	2097152 KB

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;
                            }
                            if (maxright < maxleft)
                            {
                                for (int cntright = 1; cntright <= maxright; ++cntright)
                                {
                                    if (dp[node][cntright][color2] > k)
                                    {
                                        continue;
                                    }
                                    for (int cntleft = 1; cntleft <= maxleft; ++cntleft)
                                    {
                                        merged[cntleft + cntright] = min(merged[cntleft + cntright], dp[node][cntleft][color] + dp[i.first][cntright][color2]);
                                    }
                                }
                            }
                            else
                            {
                                for (int cntleft = 1; cntleft <= maxleft; ++cntleft)
                                {
                                    if (dp[node][cntleft][color] > k)
                                    {
                                        continue;
                                    }
                                    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 / 0.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct

Subtask #1
0.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	933 ms	2097152 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct

Subtask #3
0.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	2 ms	1368 KB	Output is correct
13	Correct	2 ms	1368 KB	Output is correct
14	Correct	1 ms	1368 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	2 ms	1624 KB	Output is correct
17	Correct	2 ms	1624 KB	Output is correct
18	Incorrect	1 ms	348 KB	6th lines differ - on the 1st token, expected: '29', found: '26'
19	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	2 ms	1368 KB	Output is correct
13	Correct	2 ms	1368 KB	Output is correct
14	Correct	1 ms	1368 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	2 ms	1624 KB	Output is correct
17	Correct	2 ms	1624 KB	Output is correct
18	Incorrect	1 ms	348 KB	6th lines differ - on the 1st token, expected: '29', found: '26'
19	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
8	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	2 ms	1368 KB	Output is correct
14	Correct	2 ms	1368 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1368 KB	Output is correct
17	Correct	2 ms	1624 KB	Output is correct
18	Correct	2 ms	1624 KB	Output is correct
19	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
20	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	2 ms	1368 KB	Output is correct
14	Correct	2 ms	1368 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1368 KB	Output is correct
17	Correct	2 ms	1624 KB	Output is correct
18	Correct	2 ms	1624 KB	Output is correct
19	Incorrect	1 ms	348 KB	6th lines differ - on the 1st token, expected: '29', found: '26'
20	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	2 ms	1368 KB	Output is correct
14	Correct	2 ms	1368 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1368 KB	Output is correct
17	Correct	2 ms	1624 KB	Output is correct
18	Correct	2 ms	1624 KB	Output is correct
19	Incorrect	1 ms	348 KB	6th lines differ - on the 1st token, expected: '29', found: '26'
20	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	600 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	600 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	600 KB	Output is correct
13	Correct	2 ms	1368 KB	Output is correct
14	Correct	2 ms	1368 KB	Output is correct
15	Correct	1 ms	1368 KB	Output is correct
16	Correct	1 ms	1368 KB	Output is correct
17	Correct	2 ms	1624 KB	Output is correct
18	Correct	2 ms	1624 KB	Output is correct
19	Incorrect	1 ms	348 KB	6th lines differ - on the 1st token, expected: '29', found: '26'
20	Halted	0 ms	0 KB	-

답안 #845620

Compilation message