| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1259202 | onbert | Closing Time (IOI23_closing) | C++20 | 0 ms | 0 KiB |
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
int val, j, id;
bool operator < (const thing b) const {
if (val != b.val) return val < b.val;
if (j != b.j) return j < b.j;
return id < b.id;
}
};
const int maxn = 2e5 + 5, INF = 2e18 + 10;
int n, X, Y, k, D;
vector<pair<int,int>> adj[maxn];
int dist[maxn][2], state[maxn];
int cost1[maxn], cost2[maxn];
void dfs(int u, int j) {
for (auto [v, w]:adj[u]) if (dist[v][j] == -1) {
dist[v][j] = dist[u][j] + w;
dfs(v, j);
}
}
map<int, vector<pair<int,int>>> mp;
set<pair<int,int>> s1, s2;
vector<thing> ord;
int dc(thing x) {return lower_bound(ord.begin(), ord.end(), x) - ord.begin();}
int sz;
int fen[maxn * 3][2];
void update1(int id, int val, int j) {
while (id <= sz) {
fen[id][j] += val;
id += (id & -id);
}
}
int qry1(int id, int j) {
int val = 0;
while (id >= 1) {
val += fen[id][j];
id -= (id & -id);
}
return val;
}
multiset<int> hv1;
int ans, added, curans;
void update(int u, int x) {
if (state[u] == 1) {
int pos = dc({cost1[u], 1, u});
update1(pos, -cost1[u], 0);
update1(pos, -1, 1);
hv1.erase(hv1.find(cost1[u]));
s1.erase({cost1[u], u});
} else if (state[u] == 2) {
int pos = dc({cost2[u]/2, 2, u});
update1(pos, -cost2[u]/2, 0);
update1(pos, -1, 1);
pos++;
update1(pos, -cost2[u]/2, 0);
update1(pos, -1, 1);
s2.erase({cost2[u], u});
} else if (state[u] == 3) {
added -= cost1[u];
curans--;
} else if (state[u] == 4) {
added -= cost2[u];
curans -= 2;
}
state[u] = x;
if (x == 1) {
int pos = dc({cost1[u], 1, u});
update1(pos, cost1[u], 0);
update1(pos, 1, 1);
hv1.insert(cost1[u]);
s1.insert({cost1[u], u});
} else if (x == 2) {
int pos = dc({cost2[u]/2, 2, u});
update1(pos, cost2[u]/2, 0);
update1(pos, 1, 1);
pos++;
update1(pos, cost2[u]/2, 0);
update1(pos, 1, 1);
s2.insert({cost2[u], u});
} else if (x == 3) {
added += cost1[u];
curans++;
} else if (x == 4) {
added += cost2[u];
curans += 2;
}
}
int qry() {
int l = 0, r = sz;
while (l < r) {
int mid = (l + r + 1) / 2;
if (qry1(mid, 0) + curans <= k) l = mid;
else r = mid - 1;
}
int u = ord[l].id;
if ((qry1(l, 1) - qry(l-1, 1)) && state[u] == 2 && l + 1 <= sz && ord[l+1].id == u) {
if (qry1(l-1, 0) + *hv1.upper_bound(cost2[u]/2) > k && qry1(l+1, 0) - *prev(hv1.upper_bound(cost2[u]/2)) > k) {
return qry1(l, 1) - 1;
}
}
return qry1(l, 1);
}
int32_t max_score(int32_t N, int32_t XX, int32_t YY, int K, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
n = N, X = XX, Y = YY, k = K * 2;
for (int i=0;i<n;i++) adj[i].clear();
for (int i=0;i<U.size();i++) {
adj[U[i]].push_back({V[i], W[i] * 2});
adj[V[i]].push_back({U[i], W[i] * 2});
}
for (int i=0;i<n;i++) for (int j=0;j<=1;j++) dist[i][j] = -1;
dist[X][0] = 0;
dfs(X, 0);
dist[Y][1] = 0;
dfs(Y, 1);
D = dist[Y][0];
ord = {{0, -1, -1}};
mp.clear();
while (s1.size()) s1.erase(s1.begin());
while (s2.size()) s2.erase(s2.begin());
while (hv1.size()) hv1.erase(hv1.begin());
hv1.insert(-INF); hv1.insert(INF);
for (int i=0;i<n;i++) {
cost1[i] = min(dist[i][0], dist[i][1]);
cost2[i] = max(dist[i][0], dist[i][1]);
int del = cost2[i] - cost1[i];
mp[del].push_back({cost1[i], i});
ord.push_back({cost1[i], 1, i});
ord.push_back({cost2[i]/2, 2, i});
ord.push_back({cost2[i]/2, 2, i});
state[i] = 0;
}
sort(ord.begin(), ord.end());
sz = (int)ord.size() - 1;
for (int i=1;i<=sz;i++) fen[i][0] = fen[i][1] = 0;
added = 0, curans = 0;
for (int i=0;i<n;i++) update(i, 1);
ans = qry();
for (int i=0;i<n;i++) {
if (cost1[i] + cost2[i] == D) update(i, 3);
else update(i, 1);
}
for (auto [del, vec]:mp) {
sort(vec.begin(), vec.end());
for (auto [x, i]:vec) {
update(i, 4);
if (added <= k) ans = max(qry() + curans, ans);
}
for (auto [x, i]:vec) {
if (cost1[i] + cost2[i] == D) update(i, 4);
else update(i, 2);
}
}
return ans;
}