| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 840628 | arbuzick | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 2e5 + 5;
constexpr long long inf = (long long)(1e18) + 7;
vector<pair<int, int>> g[maxn];
long long dist_x[maxn], dist_y[maxn];
int prv[maxn];
vector<int> path;
void dfs(int v, long long* dist) {
for (auto [u, c] : g[v]) {
if (u != prv[v]) {
prv[u] = v;
dist[u] = dist[v] + c;
dfs(u, dist);
}
}
}
void calc_dist(int x, int y) {
prv[x] = x;
dfs(x, dist_x);
prv[y] = y;
dfs(y, dist_y);
int nw = x;
while (nw != y) {
path.push_back(nw);
nw = prv[nw];
}
path.push_back(y);
}
bool used[maxn];
constexpr int maxn2 = 3005;
vector<long long> dp[maxn2][4];
long long res[maxn2 * 2], pr_res[maxn2 * 2], suff_res[maxn2][maxn * 2];
int sz[maxn];
void calc_sz(int v, int prv) {
sz[v] = 1;
for (auto [u, c] : g[v]) {
if (!used[u] && u != prv) {
calc_sz(u, v);
sz[v] += sz[u];
}
}
}
void calc_dp(int v, int prv) {
int mx = 2;
for (auto [u, c] : g[v]) {
if (!used[u] && u != prv) {
calc_dp(u, v);
for (int mask = 0; mask < 4; ++mask) {
for (int cnt_nw = mx; cnt_nw >= 0; --cnt_nw) {
if (dp[v][mask][cnt_nw] == inf) {
continue;
}
for (int cnt_add = 0; cnt_add <= sz[u] * 2 && cnt_nw + cnt_add <= sz[v] * 2; ++cnt_add) {
dp[v][mask][cnt_nw + cnt_add] = min(dp[v][mask][cnt_nw + cnt_add], dp[v][mask][cnt_nw] + dp[u][mask][cnt_add]);
}
}
}
mx += sz[u] * 2;
}
}
for (int cnt = 0; cnt <= sz[v] * 2; ++cnt) {
dp[v][1][cnt] = min(dp[v][1][cnt], dp[v][0][cnt]);
dp[v][2][cnt] = min(dp[v][2][cnt], dp[v][0][cnt]);
dp[v][3][cnt] = min(dp[v][3][cnt], min(dp[v][1][cnt], dp[v][2][cnt]));
}
}
int max_score(int n, int x, int y, long long k, vector<int> u,
vector<int> v, vector<int> w) {
path.clear();
for (int i = 0; i < n; ++i) {
g[i].clear();
dist_x[i] = dist_y[i] = 0;
used[i] = false;
}
for (int i = 0; i < n - 1; ++i) {
g[u[i]].emplace_back(v[i], w[i]);
g[v[i]].emplace_back(u[i], w[i]);
}
calc_dist(x, y);
int ans = 0;
long long k_old = k;
multiset<long long> ms;
for (int i = 0; i < n; ++i) {
ms.insert(dist_x[i]);
ms.insert(dist_y[i]);
}
while (!ms.empty() && *ms.begin() <= k) {
k -= *ms.begin();
ms.erase(ms.begin());
ans++;
}
if (n > maxn2) {
return ans;
}
k = k_old;
for (auto v : path) {
used[v] = true;
calc_sz(v, v);
}
for (int i = 0; i < n; ++i) {
for (int mask = 0; mask < 4; ++mask) {
dp[i][mask].assign(sz[i] * 2 + 1, inf);
dp[i][mask].shrink_to_fit();
}
dp[i][0][0] = 0;
dp[i][1][1] = dist_x[i];
dp[i][1][2] = dist_y[i];
dp[i][2][3] = max(dist_x[i], dist_y[i]);
}
for (auto v : path) {
for (int mask = 0; mask < 4; ++mask) {
dp[v][mask].assign(sz[v] * 2 + 1, inf);
dp[v][mask][0] = 0;
}
calc_dp(v, v);
// cout << "!" << ' ' << v << ' ' << dp[v][2][0] << ' ' << dp[v][2][1] << ' ' << dp[v][2][2] << ' ' << dp[v][2][3] << endl;
}
pr_res[0] = 0;
for (int i = 1; i <= n * 2; ++i) {
pr_res[i] = inf;
}
suff_res[path.size()][0] = 0;
for (int i = 1; i <= n * 2; ++i) {
suff_res[path.size()][i] = inf;
}
for (int i = (int)path.size() - 1; i >= 0; --i) {
for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
suff_res[i][cnt_nw] = suff_res[i + 1][cnt_nw];
if (suff_res[i + 1][cnt_nw] == inf) {
continue;
}
for (int cnt_add = 0; cnt_add <= sz[path[i]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
suff_res[i][cnt_nw + cnt_add] = min(suff_res[i][cnt_nw + cnt_add], suff_res[i + 1][cnt_nw] + dp[path[i]][2][cnt_add]);
}
}
}
for (int l = 0; l < (int)path.size(); ++l) {
for (int i = 0; i <= n * 2; ++i) {
res[i] = pr_res[i];
}
for (int r = l + 1; r <= (int)path.size(); ++r) {
int add_ans = 0;
long long add_k = 0;
for (int i = 0; i < l; ++i) {
add_ans++;
add_k += dist_x[path[i]];
}
for (int i = l; i < r; ++i) {
add_ans += 2;
add_k += max(dist_x[path[i]], dist_y[path[i]]);
if (i == r - 1) {
for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
if (res[cnt_nw] == inf) {
continue;
}
for (int cnt_add = 0; cnt_add <= sz[path[i]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
res[cnt_nw + cnt_add] = min(res[cnt_nw + cnt_add], res[cnt_nw] + dp[path[i]][3][cnt_add]);
}
}
}
}
for (int i = r; i < (int)path.size(); ++i) {
add_ans++;
add_k += dist_y[path[i]];
}
while (true) {
bool change = false;
if (add_k > k) {
break;
}
if (add_ans > ans) {
ans = add_ans;
}
for (int cnt = 0; cnt <= n * 2; ++cnt) {
while (ans < n * 2) {
if (res[cnt] + add_k + suff_res[r][ans + 1 - cnt - add_ans] <= k) {
change = true;
ans++;
} else {
break;
}
}
}
if (!change) {
break;
}
}
}
for (int cnt_nw = n * 2; cnt_nw >= 0; --cnt_nw) {
if (pr_res[cnt_nw] == inf) {
continue;
}
for (int cnt_add = 0; cnt_add <= sz[path[l]] * 2 && cnt_nw + cnt_add <= n * 2; ++cnt_add) {
pr_res[cnt_nw + cnt_add] = min(pr_res[cnt_nw + cnt_add], pr_res[cnt_nw] + dp[path[l]][1][cnt_add]);
}
}
}
return ans;
}