Submission #840461

#	Time	Username	Problem	Language	Result	Execution time	Memory
840461		TheLostCookie	Closing Time (IOI23_closing)	C++17	83 / 100	179 ms	31832 KiB

closing

#include "closing.h"
#include <algorithm>
#include <functional>
#include <vector>

int max_score(int N, int X, int Y, long long int K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
	std::vector<std::vector<std::pair<int,long long int>>> adj(N);
	for(int i = 0; i < N-1; i++) {
		adj[U[i]].emplace_back(V[i],W[i]);
		adj[V[i]].emplace_back(U[i],W[i]);
	}
	std::vector<long long int> dX(N), dY(N);
	
	auto dfs = [&](auto &&self, std::vector<long long int> &d, int u, int p)->void{
		for(auto [v,w]: adj[u]) {
			if(v != p) {
				d[v] = d[u]+w;
				self(self,d,v,u);
			}
		}
		return;
	};
	
	dfs(dfs,dX,X,-1);
	dfs(dfs,dY,Y,-1);
	
	int ans = 0;
	//Case: No overlap
	{
		std::vector<long long int> d(dX);
		d.reserve(2*N);
		for(int i = 0; i < N; i++) {
			d.push_back(dY[i]);
		}
		std::sort(d.begin(),d.end());
		long long int sum = 0;
		while(ans<2*N && sum+d[ans]<=K) sum+=d[ans++];
	}
	//Case: XY bridge
	{
		std::vector<long long int> freeChoices;
		std::vector<std::pair<long long int,long long int>> pairChoices;
		long long int xy = 0;
		int xyLen = 0;
		for(int i = 0; i < N; i++) {
			long long int d0 = std::min(dX[i],dY[i]);
			long long int d1 = std::max(dX[i],dY[i]);
			if(d0+d1 == dX[Y]) {
				xy += d0;
				xyLen++;
				freeChoices.push_back(d1-d0);
			} else if(d0 <= d1-d0) {
				freeChoices.push_back(d0);
				freeChoices.push_back(d1-d0);
			} else {
				pairChoices.emplace_back(d0,d1-d0);
			}
		}
		
		std::sort(freeChoices.begin(), freeChoices.end());
		for(int i = 0; i < int(freeChoices.size())-1; i++) {
			freeChoices[i+1] += freeChoices[i];
		}
		
		auto tryCase = [&](long long int d) {
			long long int k = K-xy-d;
			if(k<0) return -2*N; //Invalid case
			
			int ret = (std::upper_bound(freeChoices.begin(),freeChoices.end(),k)-freeChoices.begin());
			return ret;
		};
		
		std::sort(pairChoices.begin(), pairChoices.end(),[](std::pair<int,int> a, std::pair<int,int> b){return a.first+a.second<b.first+b.second;});
		
		int pn = pairChoices.size();
		if(pn == 0) {
			ans = std::max(ans,xyLen+tryCase(0));
		} else {
			std::vector<long long int> prefMax(pn), suffMin(pn);
			prefMax[0] = pairChoices[0].second;
			for(int i = 1; i < pn; i++) {
				prefMax[i] = std::max(prefMax[i-1],pairChoices[i].second);
			}
			suffMin[pn-1] = pairChoices[pn-1].first;
			for(int i = pn-2; i >= 0; i--) {
				suffMin[i] = std::min(suffMin[i+1],pairChoices[i].first);
			}
			
			long long int prefPairs = 0;
			for(int i = 0; i <= pn; i++) {
				//Case: i of the pairs are chosen.
				ans = std::max(ans,xyLen+2*i+tryCase(prefPairs));
				//Case: i of the pairs less one are chosen
				if(i) {
					ans = std::max(ans,xyLen+2*i-1+tryCase(prefPairs-prefMax[i-1]));
				}
				//Case: i of the pairs more one are chosen
				if(i != pn) {
					ans = std::max(ans,xyLen+2*i+1+tryCase(prefPairs+suffMin[i]));
					prefPairs += (pairChoices[i].first+pairChoices[i].second);
				}
			}
		}
	}
	
	return ans;
}

• 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: 0 / 17