Submission #1258953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258953		nickolasarapidis	Closing Time (IOI23_closing)	C++17	0 / 100	117 ms	26292 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second

const int MAXN = 200000;

vector<pair<int, int>> adj[MAXN];
vector<ll> disX(MAXN), disY(MAXN);

void dfsX(int s, int e, int d){
	disX[s] = d;
	for(auto u : adj[s]){
		if(u.F != e){
			dfsX(u.F, s, d + u.S);
		}
	}
}

void dfsY(int s, int e, int d){
	disY[s] = d;
	for(auto u : adj[s]){
		if(u.F != e){
			dfsY(u.F, s, d + u.S);
		}
	}
}

int max_score(int N, int X, int Y, ll K, vector<int> u, vector<int> v, vector<int> w){
  for(int i = 0; i < N; i++){
    adj[i].clear();
  }
	for(int i = 0; i < N - 1; i++){
		adj[u[i]].push_back({v[i], w[i]});
		adj[v[i]].push_back({u[i], w[i]});
	}
	dfsX(X, -1, 0);
	dfsY(Y, -1, 0);
	priority_queue<ll> q;
	for(int i = 0; i < N; i++){
		q.push(-disX[i]);
		q.push(-disY[i]);
	}
	int ans = 0, sum = 0;
	while(!q.empty()){
		if(sum - q.top() <= K){
			sum -= q.top();
			ans++;
			q.pop();
		}
		else{
			break;
		}
	}
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 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