# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1222217 | nickolasarapidis | 봉쇄 시간 (IOI23_closing) | C++17 | 0 ms | 0 KiB |
#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){
dfs(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){
dfs(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 - 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();
q.pop();
}
else{
break;
}
}
return ans;
}