Submission #1241444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241444		vako_p	Closing Time (IOI23_closing)	C++20	21 / 100	1097 ms	49204 KiB

closing

#include "closing.h"
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")

const int mxN = 3e5 + 5;
ll n,dis[mxN],dis1[mxN],dis2[mxN];
vector<pair<ll,ll>> v[mxN];
vector<ll> vv;

void dfs(ll at, ll par, bool ok = false){
	if(ok) vv.pb(at);
	for(auto it : v[at]){
		if(it.ff == par) continue;
		dis[it.ff] = dis[at] + it.sd;
		dfs(it.ff, at, ok);
	}
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = N;
    for(int i = 0; i < n - 1; i++){
    	v[U[i]].pb({V[i], W[i]});
    	v[V[i]].pb({U[i], W[i]});
	}
	ll root = 0;
	for(int i = 0; i < n; i++) if(v[i].size() == 1){
		root = i;
		break;
	} 
	dis[root] = 0;
	vv.clear();
	dfs(root, root, true);
	int x,y;
	for(int i = 0; i < n; i++){
		if(vv[i] == X) x = i;
		if(vv[i] == Y) y = i;
	}
	if(x > y) swap(x, y);
	dis[X] = 0;
	dfs(X, X);
	for(int i = 0; i < n; i++) dis1[i] = dis[vv[i]];
	dis[Y] = 0;
	dfs(Y, Y);
	for(int i = 0; i < n; i++) dis2[i] = dis[i];
	for(int i = 0; i < n; i++) dis[i] = dis2[vv[i]];
	ll sum = 0,ans = 0;
	vector<ll> v2;
	for(int i = 0; i < n; i++){
		v2.pb(dis[i]);
		v2.pb(dis1[i]);
	}
	sort(v2.begin(), v2.end());
	for(auto it : v2){
		sum += it;
		if(sum > K) break;
		ans++;
	}
	for(int l = 0; l <= y; l++){
		multiset<pair<ll,ll>> s;
		stack<pair<ll,ll>> s1;
		sum = 0;
		ll ans1 = 2 * max(1, x - l + 1),sum1 = 0; 
		for(int i = 0; i < l; i++){
			s.insert({dis[i], 0});
			sum1 += dis[i];
		}
		for(int i = y + 1; i < n; i++){
			s.insert({dis[i], 0});
			sum1 += dis[i];
		}
		for(int i = 0; i < min(x, l); i++){
			s.insert({dis1[i], 1});
			sum1 += dis1[i];
		}
		for(int i = max(l, x) + 1; i < n; i++){
			if(i <= y){
				ans1++;
				sum += dis[i];
			}
			sum1 += dis1[i];
			s.insert({dis1[i], 1});
		}
		for(int i = x; i < l; i++){
			ans1++;
			sum += dis1[i];
		}
		for(int i = l; i <= max(l, x); i++) sum += max(dis[i], dis1[i]);
		if(sum > K) continue;
		while(sum + sum1 > K){
			auto it = s.end(); --it;
			s1.push(*it);
			sum1 -= (*it).ff;
			s.erase(it);
		}
		ans = max(ans, ans1 + (ll)s.size());
		for(int r = max(l, x) + 1; r < n; r++){
			auto it = s.find({dis[r], 0}),it1 = s.find({dis1[r], 1}); 
			if(it != s.end()){
				sum1 -= (*it).ff;
				s.erase(it);
			}
			if(it1 != s.end()){
				sum1 -= (*it1).ff;
				s.erase(it1);
			}
			if(r <= y){
				sum -= dis[r];
				ans1--;
			}
			ans1 += 2;
			sum += max(dis[r], dis1[r]);
			if(sum > K) break;	
			while(sum + sum1 > K){
				auto it2 = s.end(); --it2;
				s1.push(*it2);
				sum1 -= (*it2).ff;
				s.erase(it2);
			}	
			while(s1.size()){
				auto it2 = s1.top();
				if(it2.ff + sum1 + sum > K) break;
				sum1 += it2.ff;
				s.insert(it2);
				s1.pop();
			}	
			ans = max(ans, ans1 + (ll)s.size());
		}
	}
	for(int i = 0; i < n; i++) v[i].clear();
//	cout << "aa" << endl;
	return ans;
}

//1
//6 0 3 10
//5 3 5
//3 1 2
//1 2 1
//2 0 3
//0 4 7

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