Submission #1241477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241477		vako_p	Closing Time (IOI23_closing)	C++20	35 / 100	1092 ms	47956 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++){
		vector<pair<ll,pair<ll,ll>>> ss;
		stack<pair<ll,pair<ll,ll>>> s1,st;
		sum = 0;
		ll ans1 = 2 * max(1, x - l + 1),sum1 = 0; 
		for(int i = 0; i < l; i++){
			ss.pb({dis[i], {0, i}});
//			sum1 += dis[i];
		}
		for(int i = y + 1; i < n; i++){
			ss.pb({dis[i], {0, i}});
//			sum1 += dis[i];
		}
		for(int i = 0; i < min(x, l); i++){
			ss.pb({dis1[i], {1, i}});
//			sum1 += dis1[i];
		}
		for(int i = max(l, x) + 1; i < n; i++){
			if(i <= y){
				ans1++;
				sum += dis[i];
			}
//			sum1 += dis1[i];
			ss.pb({dis1[i], {1, i}});
		}
		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;
		ll idx = 0;
		sort(ss.begin(), ss.end());
		vector<vector<bool>> vis(n, vector<bool>(2, false));
		ll curr = 0;
		for(int i = 0; i < ss.size(); i++){
			if(sum + sum1 + ss[i].ff <= K){
				sum1 += ss[i].ff;
				vis[ss[i].sd.sd][ss[i].sd.ff] = true;
				st.push(ss[i]);
			}
			else{
				idx = i;
				break;
			}
		}
		if(ss.size()) for(int i = ss.size() - 1; i >= idx; i--){
			s1.push(ss[i]);
		}
//		while(sum + sum1 > K){
//			auto it = ss.end(); --it;
//			s1.push(*it);
//			sum1 -= (*it).ff;
//			ss.erase(it);
//		}
		ans = max(ans, ans1 + (ll)st.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(vis[r][0]){
				sum1 -= dis[r];
				curr++;
				vis[r][0] = false;
//				s.erase(it);
			}
			if(vis[r][1]){
				sum1 -= dis1[r];
				curr++;
				vis[r][1] = false;
//				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){
				pair<ll,pair<ll,ll>> it2 = st.top();
				st.pop();
				if(!vis[it2.sd.sd][it2.sd.ff]){
					curr--;
					continue;
				}
				vis[it2.sd.sd][it2.sd.ff] = false;
				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;
				st.push(it2);
				vis[it2.sd.sd][it2.sd.ff] = true;
				s1.pop();
			}	
			ans = max(ans, ans1 + (ll)st.size() - curr);
		}
	}
	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: 14 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17