제출 #841003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841003		jhwest2	Closing Time (IOI23_closing)	C++17	43 / 100	129 ms	26276 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);
	}
}
bool dead[MAXN];
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;
		// cout << ((t == 0) ? "X" : "Y") << ' ' << c << ' ' << "vertex " << v << "??\n";
		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;
	while (!pq.empty()) pq.pop();
	long long t = 0;
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			t += min(dx[i], dy[i]);
			++ans2;
			dead[i] = true;
		}
	}
	for (int i = 0; i < N; i++) {
		if (dx[i] + dy[i] == D) {
			for (auto [w, x] : g[i]) if (!dead[x]) {
				if (dx[x] <= dy[x]) {
					pq.push({-dx[x], x, i, 0});
				}
				else {
					pq.push({-dy[x], x, i, 1});
				}
			}
		}
	}
	pq.push({dy[vy] - dx[vy], vy, vx, 0});
	pq.push({dx[vx] - dy[vx], vx, vy, 1});
	if (t <= K) {
		K -= t;
		// cout << "we have " << K << '\n';
		while (!pq.empty()) {
			auto [c, v, p, t] = pq.top();
			pq.pop();
			c = -c;
			// if (t != 2) {
			// 	cout << ((t == 0) ? "X" : "Y") << ' ' << "cost " << c << ' ' << "vertex " << v << '\n';
			// 	if (dead[v]) cout << "Progess\n";
			// 	else cout << "New\n";
			// }
			// else {
			// 	cout << "Upgrade " << v << "with cost " << c << '\n';
			// }
			if (c > K) break;
			
			K -= c;
			++ans2;
			if (t == 2) continue;
			if (!dead[v]) {
				if (t == 0) pq.push({dx[v] - dy[v], v, p, 2});
				else pq.push({dy[v] - dx[v], v, p, 2});
				for (auto [w, x] : g[v]) if (p != x) {
					if (t == 0) pq.push({-dx[x], x, v, 0});
					else pq.push({-dy[x], x, v, 1});
				}
			}
			else {
				for (auto [w, x] : g[v]) if (p != x) {
					if (dead[x]) {
						if (t == 0) pq.push({-dx[x] + dy[x], x, v, 0});
						else pq.push({-dy[x] + dx[x], x, v, 1});
					}
				}
			}
		}
		ans1 = max(ans1, ans2);
	}
	for (int i = 0; i < N; i++) g[i].clear(), dead[i] = false;
	return ans1;
}

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