#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;
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)] + 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1038 ms |
35876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
600 KB |
Output is correct |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
600 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '173', found: '172' |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
388 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
600 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '173', found: '172' |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
