#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
vl calc_dist(int X, vector<vector<pii>> edges) {
int N = sz(edges);
vl dist(N, 1e12);
vi vis(N);
priority_queue<pli, vector<pli>, greater<pli>> pq;
pq.push({0,X});
dist[X] = 0;
while(!pq.empty()) {
auto [D,at] = pq.top();
pq.pop();
if(vis[at]) continue;
vis[at] = 1;
for(auto [viz, peso] : edges[at]) {
if(dist[viz] > D + peso) {
dist[viz] = D + peso;
pq.push({D+peso, viz});
}
}
}
return dist;
}
int max_score(int N, int X, int Y, ll K, vi U, vi V, vi W) {
vector<vector<pii>> edges(N);
for(int i = 0; i+1 < N; i++)
edges[U[i]].pb({V[i], W[i]}), edges[V[i]].pb({U[i], W[i]});
vl distX = calc_dist(X, edges), distY = calc_dist(Y, edges);
set<pli> cam, twice;
for(int i = 0; i < N; i++) {
if(distX[Y] == distX[i] + distY[i])
cam.insert({min(distX[i], distY[i]), i});
}
int t = sz(cam);
vl dp(2*N+1, 1e18+1);
dp[0] = 0;
ll at_val = 0;
while(!cam.empty()) {
auto [D, ind] = *cam.begin();
cam.erase(cam.begin());
twice.insert({distX[Y] - 2*D, ind});
at_val += D;
dp[t - sz(cam)] = at_val;
}
while(!twice.empty()) {
auto [D, ind] = *twice.begin();
twice.erase(twice.begin());
at_val += D;
dp[2*t - sz(twice)] = at_val;
}
for(int i = 0; i < N; i++) {
if(distX[Y] == distX[i] + distY[i]) continue;
int mi = min(distX[i], distY[i]), ma = max(distX[i], distY[i]);
for(int qtd = 2*N; qtd > 0; qtd--)
dp[qtd] = min({dp[qtd], dp[qtd-1] + mi, dp[qtd-2] + ma});
}
for(int qtd = 2*N; qtd > 0; qtd--)
if(dp[qtd] <= K) return qtd;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |