Submission #841022

#	Time	Username	Problem	Language	Result	Execution time	Memory
841022		jhwest2	Closing Time (IOI23_closing)	C++17	100 / 100	171 ms	32312 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 202020;

long long dx[MAXN], dy[MAXN];
vector<pair<int, int>> g[MAXN];

void dfs_x(int p, int v) {
	for (auto [w, x] : g[v]) if (p != x) {
		dx[x] = dx[v] + w;
		dfs_x(v, x);
	}
}
void dfs_y(int p, int v) {
	for (auto [w, x] : g[v]) if (p != x) {
		dy[x] = dy[v] + w;
		dfs_y(v, x);
	}
}
int max_score(int N, int X, int Y, long long K,
              vector<int> U, vector<int> V, vector<int> W)
{
	for (int i = 0; i < N - 1; i++) {
		g[U[i]].push_back({W[i], V[i]});
		g[V[i]].push_back({W[i], U[i]});
	}
	dx[X] = 0;
	dy[Y] = 0;
	dfs_x(-1, X);
	dfs_y(-1, Y);
	long long D = dx[Y];
	long long vx = X;
	long long vy = Y;
	long long tx = 0;
	long long ty = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			if (dx[i] <= dy[i] && tx < dx[i]) {
				vx = i;
				tx = dx[i];
			}
			if (dx[i] > dy[i] && ty < dy[i]) {
				vy = i;
				ty = dy[i];
			}
		}
	}
	// no overlap
	priority_queue<tuple<long long, int, int, int>> pq;
	pq.push({0, X, -1, 0});
	pq.push({0, Y, -1, 1});
	int ans1 = 0;
	long long tk = K;
	while (!pq.empty()) {
		auto [c, v, p, t] = pq.top();
		pq.pop();
		c = -c;
		if (c > K) break;
		K -= c;
		++ans1;
		for (auto [w, x] : g[v]) if (p != x) {
			if ((v == vx && x == vy) || (v == vy && x == vx)) continue;
			if (t == 0)
				pq.push({-dx[x], x, v, 0});
			else
				pq.push({-dy[x], x, v, 1});
		}
	}
	// yes overlap
	K = tk;
	int ans2 = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			K -= min(dx[i], dy[i]);
			++ans2;
		}
	}
	if (K >= 0) {
		vector<long long> t1;
		vector<pair<long long, long long>> t2;
		for (int i = 0; i < N; i++) {
			if (dx[i] + dy[i] == D) {
				if (dx[i] <= dy[i]) t1.push_back(dy[i] - dx[i]);
				else t1.push_back(dx[i] - dy[i]);
			}
			else {
				if (dx[i] <= dy[i]) {
					if (dx[i] <= dy[i] - dx[i]) {
						t1.push_back(dx[i]);
						t1.push_back(dy[i] - dx[i]);
					}
					else t2.push_back({dx[i], dy[i]});
				}	
				else {
					if (dy[i] <= dx[i] - dy[i]) {
						t1.push_back(dy[i]);
						t1.push_back(dx[i] - dy[i]);
					}
					else t2.push_back({dy[i], dx[i]});					
				}
			}
		}
		sort(t1.begin(), t1.end());
		sort(t2.begin(), t2.end(), [&](auto p, auto q) {
			return p.second < q.second;
		});
		for (int i = 1; i < t1.size(); i++) t1[i] += t1[i - 1];
		int s = upper_bound(t1.begin(), t1.end(), K) - t1.begin();
		int sz = t2.size();
		if (sz != 0) {
			vector<long long> pre(sz), suf(sz), sum(sz);
			pre[0] = t2[0].second - t2[0].first;
			sum[0] = t2[0].second;
			for (int i = 1; i < sz; i++) {
				pre[i] = max(pre[i - 1], t2[i].second - t2[i].first);
				sum[i] = sum[i - 1] + t2[i].second;
			}
			suf[sz - 1] = t2[sz - 1].first;
			for (int i = sz - 1; i > 0; i--) {
				suf[i - 1] = min(suf[i], t2[i - 1].first);
			}
			if (suf[0] <= K) {
				s = max(s, 1 + (int)(upper_bound(t1.begin(), t1.end(), K - suf[0]) - t1.begin()));
			}
			for (int i = 0; i < sz; i++) {
				if (sum[i] - pre[i] <= K)
					s = max(s, 2 * i + 1 + (int)(upper_bound(t1.begin(), t1.end(), K - sum[i] + pre[i]) - t1.begin()));
				
				if (sum[i] <= K)
					s = max(s, 2 * i + 2 + (int)(upper_bound(t1.begin(), t1.end(), K - sum[i]) - t1.begin()));
				
				if (i != sz - 1 && sum[i] + suf[i + 1] <= K)
					s = max(s, 2 * i + 3 + (int)(upper_bound(t1.begin(), t1.end(), K - sum[i] - suf[i + 1]) - t1.begin()));
			}
		}
		ans1 = max(ans1, ans2 + s);
	}
	for (int i = 0; i < N; i++) {
		g[i].clear();
	}
	return ans1;
}

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 1; i < t1.size(); i++) t1[i] += t1[i - 1];
      |                   ~~^~~~~~~~~~~

• 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