| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1351398 | trimkus | Souvenirs (IOI25_souvenirs) | C++20 | 0 ms | 0 KiB |
#include "souvenirs.h"
#include "debug.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
void buy_souvenirs(int N, long long P0) {
vector<ll> sum(N);
vector<int> cnt(N);
int left = N - 1;
vector<vector<int>> dep(N);
dep[0].push_back(0);
sum[0] = P0;
auto relax = [&](ll y) -> void {
auto now = transaction(y);
assert(sz(now.first) > 0);
int x = now.first[0];
// cerr << x << " " << y << "=";dbg(now);
vector<int> add;
ll cost = y - now.second;
assert(now.first[0] == x);
for (int i : now.first) {
cnt[i] += 1;
if (i != x && sz(dep[i]) == 1) {
cost -= sum[i];
} else {
add.push_back(i);
}
}
sum[x] = cost;
dep[x] = add;
};
auto update = [&]() -> void {
for (int i = N - 1; i >= 0; --i) {
vector<int> add;
ll cost = sum[i];
for (int j : dep[i]) {
if (j == i) {
add.push_back(j);
continue;
}
if (sz(dep[j]) == 1) cost -= sum[j];
else add.push_back(j);
}
dep[i] = add;
sum[i] = cost;
// cerr<<i<<",sum="<<sum[i]<<",dep=";dbg(dep[i]);
}
};
while (left > 0) {
for (int i = N - 1; i >= 0; --i) {
if (sz(dep[i]) == 0) {
while (sz(dep[i]) == 0) i -= 1;
relax(sum[i] / sz(dep[i]) - (sz(dep[i]) == 1));
break;
}
}
update();
left = N;
for (int i = 0; i < N; ++i) {
if (sz(dep[i]) == 1) left -= 1;
}
}
for (int i = 0; i < N; ++i) {
while (cnt[i] < i) {
cnt[i] += 1;
transaction(sum[i]);
}
}
}