Submission #1081956

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1081956	2024-08-30T13:15:56 Z	Boas	Closing Time (IOI23_closing)	C++17	21 / 100	1000 ms	35668 KB

closing

#include "closing.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T1, typename T2>
using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef pair<int, int> ii;
typedef signed i32;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

// #pragma GCC optimize("trapv")

int sum(vi &pSum, int a, int b)
{
    int l = min(a, b), r = max(a, b);
    return pSum[r + 1] - pSum[l];
}

i32 max_score(i32 N, i32 X, i32 Y, int K, vi32 U, vi32 V, vi32 W)
{
    vvii adj(N);
    loop(N - 1, i)
    {
        adj[U[i]].pb({V[i], W[i]});
        adj[V[i]].pb({U[i], W[i]});
    }
    vi xTime(N), yTime(N);
    auto dfs = [&](auto &&self, int i, int prev, vi &time) -> void
    {
        for (auto [j, w] : adj[i])
        {
            if (j == prev)
                continue;
            time[j] = time[i] + w;
            self(self, j, i, time);
        }
    };
    dfs(dfs, X, X, xTime);
    dfs(dfs, Y, Y, yTime);
    vi maxTime(N);
    loop(N, i) maxTime[i] = max(xTime[i], yTime[i]);
    vi pSumX = {0}, pSumY = {0}, pSumMax = {0};
    loop(N, i)
    {
        pSumX.pb(pSumX.back() + xTime[i]);
        pSumY.pb(pSumY.back() + yTime[i]);
        pSumMax.pb(pSumMax.back() + maxTime[i]);
    }
    int res = 0;
    for (int lx = X; lx >= 0; lx--)
    {
        for (int rx = X; rx < N; rx++)
        {
            for (int ly = Y; ly >= 0; ly--)
            {
                int sumX = 0, sumY = 0, sumBoth = 0;
                if (rx >= ly)
                {
                    if (lx < ly)
                    {
                        sumX += sum(pSumX, lx, ly - 1);
                    }
                    if (rx < Y)
                    {
                        sumY += sum(pSumY, rx + 1, Y);
                    }
                    sumBoth += sum(pSumMax, ly, rx);
                }
                else
                {
                    sumX += sum(pSumX, lx, rx);
                    sumY += sum(pSumY, ly, Y);
                }
                int dis = sumX + sumY + sumBoth;
                int left = K - dis;
                if (left < 0)
                    continue;
                auto it = prev(upper_bound(ALL(pSumY), pSumY[max(Y, (i32)rx) + 1] + left));
                int ry = (it - pSumY.begin()) - 1;
                int cnt = (rx - lx + 1) + (ry - ly + 1);
                res = max(res, cnt);
            }
        }
    }
    /*for (int both = 0; both < N; both++)
    {
        int best = 0, bestDis = INT_MAX;
        for (int i = X; i <= Y; i++)
        {
            int dis = sumDis(X, i) + sumDis(i, Y);
            if (dis < bestDis)
            {
                best = i;
                bestDis = dis;
            }
        }
    }*/
    return res;
}

Subtask #0
0.0 / 0.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #1
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1062 ms	35668 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	412 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	432 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	412 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	432 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	2 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	436 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	114 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	127 ms	496 KB	Output is correct
22	Correct	2 ms	348 KB	Output is correct
23	Correct	1 ms	444 KB	Output is correct
24	Correct	2 ms	348 KB	Output is correct

Subtask #4
0.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	412 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	432 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	2 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	436 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	114 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	127 ms	496 KB	Output is correct
22	Correct	2 ms	348 KB	Output is correct
23	Correct	1 ms	444 KB	Output is correct
24	Correct	2 ms	348 KB	Output is correct
25	Correct	8 ms	348 KB	Output is correct
26	Execution timed out	1098 ms	780 KB	Time limit exceeded
27	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	344 KB	1st lines differ - on the 1st token, expected: '6', found: '5'
2	Halted	0 ms	0 KB	-

Submission #1081956

Compilation message