Submission #1153548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153548		siewjh	Closing Time (IOI23_closing)	C++20	100 / 100	217 ms	47064 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const ll inf = 2e18;
vector<pair<int, ll>> adj[MAXN];
ll dx[MAXN], dy[MAXN], d1[MAXN], d2[MAXN], ss[MAXN << 1], sd[MAXN << 1];
void dfs(int x, int par, ll dist, ll *darr){
	darr[x] = dist;
	for (auto [nn, nd] : adj[x]){
		if (nn == par) continue;
		dfs(nn, x, dist + nd, darr);
	}
}
int max_score(int N, int X, int Y, ll K, vector<int> U, vector<int> V, vector<int> W){
	for (int i = 0; i < N; i++) adj[i].clear();
	for (int i = 0; i < N - 1; i++){
		int u = U[i], v = V[i], w = W[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs(X, -1, 0, dx); dfs(Y, -1, 0, dy);
	for (int i = 0; i < N; i++){
		d1[i] = min(dx[i], dy[i]);
		d2[i] = max(dx[i], dy[i]) - d1[i];
	}
	int ans1 = 0, ans2 = 0;
	ll cap = K;
	vector<ll> vl1(N);
	for (int i = 0; i < N; i++) vl1[i] = d1[i];
	sort(vl1.begin(), vl1.end());
	for (ll c : vl1){
		if (cap < c) break;
		cap -= c; ans1++;
	}
	cap = K;
	vector<ll> vs;
	vector<pair<ll, int>> vd;
	set<pair<ll, int>> reg;
	for (int i = 0; i < N; i++){
		if (dx[i] + dy[i] == dx[Y]){
			cap -= d1[i]; ans2++;
			vs.push_back(d2[i]);
		}
		else if (d1[i] > d2[i]){
			vd.push_back({d1[i] + d2[i], i});
			reg.insert({d1[i], i});
		}
		else{
			vs.push_back(d1[i]);
			vs.push_back(d2[i]);
		}
	}
	if (cap >= 0){
		sort(vs.begin(), vs.end()); sort(vd.begin(), vd.end());
		int ssz = vs.size(), dsz = vd.size();
		ss[0] = 0;
		for (int i = 0; i < ssz; i++) ss[i + 1] = ss[i] + vs[i];
		ll sub = 0;
		sd[0] = 0;
		for (int i = 0; i < dsz; i++){
			ll c; int id; tie(c, id) = vd[i];
			ll r1a2 = c - sub, a1 = inf;
			if (!reg.empty()) a1 = reg.begin()->first;
			sd[(i << 1) + 1] = sd[i << 1] + min(r1a2, a1);
			sd[(i << 1) + 2] = sd[i << 1] + c;
			sub = max(sub, d2[id]);
			reg.erase({d1[id], id});
		}
		int res = 0;
		for (int si = 0, di = (dsz << 1); si <= ssz; si++){
			while (di > 0 && ss[si] + sd[di] > cap) di--;
			if (ss[si] + sd[di] > cap) break;
			res = max(res, si + di);
		}
		ans2 += res;
	}
	else ans2 = 0;
	return max(ans1, ans2);
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 9 / 9
• Subtask 6: 11 / 11
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 17 / 17