Submission #1241384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241384		vako_p	Closing Time (IOI23_closing)	C++20	21 / 100	1098 ms	38232 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++){
		for(int r = l; r < n; r++){
			if(r < x) continue;
			sum = 0;
			vector<ll> v1;
			ll ans1 = 2 * (r - l + 1);
			for(int i = l; i <= r; i++) sum += max(dis[i], dis1[i]);
			for(int i = x; i < l; i++){
				ans1++;
				sum += dis1[i];
			}
			for(int i = r + 1; i <= y; i++){
				ans1++;
				sum += dis[i];
			}
			if(sum > K) continue;
			for(int i = 0; i < min(x, l); i++) v1.pb(dis1[i]);
			for(int i = r + 1; i < n; i++) v1.pb(dis1[i]);
			for(int i = 0; i < l; i++) v1.pb(dis[i]);
			for(int i = max(r, y) + 1; i < n; i++) v1.pb(dis[i]);
			sort(v1.begin(), v1.end());
			for(auto it : v1){
				sum += it;
				if(sum > K) break;
				ans1++;
			}
			ans = max(ans, ans1);
		}
	}
	for(int i = 0; i < n; i++) v[i].clear();
	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