This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "closing.h"
#include <algorithm>
#include <functional>
#include <vector>
int max_score(int N, int X, int Y, long long int K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
std::vector<std::vector<std::pair<int,long long int>>> adj(N);
for(int i = 0; i < N-1; i++) {
adj[U[i]].emplace_back(V[i],W[i]);
adj[V[i]].emplace_back(U[i],W[i]);
}
std::vector<long long int> dX(N), dY(N);
auto dfs = [&](auto &&self, std::vector<long long int> &d, int u, int p)->void{
for(auto [v,w]: adj[u]) {
if(v != p) {
d[v] = d[u]+w;
self(self,d,v,u);
}
}
return;
};
dfs(dfs,dX,X,-1);
dfs(dfs,dY,Y,-1);
int ans = 0;
//Case: No overlap
{
std::vector<long long int> d(dX);
d.reserve(2*N);
for(int i = 0; i < N; i++) {
d.push_back(dY[i]);
}
std::sort(d.begin(),d.end());
long long int sum = 0;
while(ans<2*N && sum+d[ans]<=K) sum+=d[ans++];
}
//Case: XY bridge
{
std::vector<long long int> freeChoices;
std::vector<std::pair<long long int,long long int>> pairChoices;
long long int xy = 0;
int xyLen = 0;
for(int i = 0; i < N; i++) {
long long int d0 = std::min(dX[i],dY[i]);
long long int d1 = std::max(dX[i],dY[i]);
if(d0+d1 == dX[Y]) {
xy += d0;
xyLen++;
freeChoices.push_back(d1-d0);
} else if(d0 <= d1-d0) {
freeChoices.push_back(d0);
freeChoices.push_back(d1-d0);
} else {
pairChoices.emplace_back(d0,d1-d0);
}
}
std::sort(freeChoices.begin(), freeChoices.end());
for(int i = 0; i < int(freeChoices.size())-1; i++) {
freeChoices[i+1] += freeChoices[i];
}
auto tryCase = [&](long long int d) {
long long int k = K-xy-d;
if(k<0) return -2*N; //Invalid case
int ret = (std::upper_bound(freeChoices.begin(),freeChoices.end(),k)-freeChoices.begin());
return ret;
};
std::sort(pairChoices.begin(), pairChoices.end(),[](std::pair<int,int> a, std::pair<int,int> b){return a.first+a.second<b.first+b.second;});
int pn = pairChoices.size();
if(pn == 0) {
ans = std::max(ans,xyLen+tryCase(0));
} else {
std::vector<long long int> prefMax(pn), suffMin(pn);
prefMax[0] = pairChoices[0].second;
for(int i = 1; i < pn; i++) {
prefMax[i] = std::max(prefMax[i-1],pairChoices[i].second);
}
suffMin[0] = pairChoices[pn-1].first;
for(int i = pn-2; i >= 0; i--) {
suffMin[i] = std::max(suffMin[i+1],pairChoices[i].second);
}
long long int prefPairs = 0;
for(int i = 0; i <= pn; i++) {
//Case: i of the pairs are chosen.
ans = std::max(ans,xyLen+2*i+tryCase(prefPairs));
//Case: i of the pairs less one are chosen
if(i) {
ans = std::max(ans,xyLen+2*i-1+tryCase(prefPairs-prefMax[i-1]));
}
//Case: i of the pairs more one are chosen
if(i != pn) {
ans = std::max(ans,xyLen+2*i+1+tryCase(prefPairs+suffMin[i]));
}
prefPairs += (pairChoices[i].first+pairChoices[i].second);
}
}
}
return ans;
}
# | 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... |