#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200'005;
vector<pair<int, ll> > adj[N];
ll dx[N];
int px[N];
int py[N];
ll dy[N];
ll d[N];
int p[N];
void dfs(int v, int par) {
p[v] = par;
for(auto& u : adj[v]) {
if(u.first == par) continue;
d[u.first] = u.second + d[v];
dfs(u.first, v);
}
}
int max_score(int n, int X, int Y, long long k,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
for(int i = 0; i < n; ++i){
d[i] = dx[i] = dy[i] = p[i] = px[i] = py[i] = 0;
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]});
}
dfs(X, -1);
swap(d, dx);
swap(p, px);
dfs(Y, -1);
swap(d, dy);
swap(p, py);
int res = 0;
vector<ll> dd;
for(int i = 0; i < n; ++i) dd.push_back(min(dx[i], dy[i]));
sort(dd.begin(), dd.end());
ll tmp = k;
for(int i = 0; i < n; ++i) {
tmp -= dd[i];
if(tmp >= 0) res = i + 1;
}
int cur = 0;
ll sum = 0;
multiset<ll> q, w;
// q - solo, w - double
vector<pair<ll, ll> > help;
for(int i = 0; i < n; ++i) {
if(dx[i] + dy[i] == dx[Y]) {
k -= min(dx[i], dy[i]);
++cur;
q.insert(abs(dx[i] - dy[i]));
if(k < 0) return res;
} else {
help.push_back({min(dx[i], dy[i]), max(dx[i], dy[i])});
q.insert(min(dx[i], dy[i]));
}
}
sort(help.begin(), help.end(), [](const pair<ll, ll>& lhs, const pair<ll, ll>& rhs) {
return lhs.second - lhs.first == rhs.second - rhs.first ? lhs.first < rhs.first : lhs.second - lhs.first < rhs.second - rhs.first;
});
auto qit = q.begin();
auto wit = w.begin();
while(qit != q.end() && sum + *qit <= k) {
++cur;
sum += *qit;
++qit;
}
res = max(res, cur);
for(auto& e : help) {
if(wit == w.end() || *wit > e.second) {
cur += 2;
sum += e.second;
}
w.insert(e.second);
if(sum > k) {
--wit;
sum -= *wit;
cur -= 2;
}
auto fin = q.find(e.first);
if(qit == w.end() || *qit >= e.first) {
cur -= 1;
sum -= e.first;
}
if(qit == fin) {
cur += 1;
sum += e.first;
++qit;
}
q.erase(fin);
bool reb = 0;
do {
while(qit != q.end() && sum + *qit <= k) {
sum += *qit;
cur += 2;
qit++;
reb = 1;
}
while(wit != w.end() && sum + *wit <= k) {
sum += *wit;
cur += 2;
wit++;
reb = 1;
}
if(wit != w.end() && qit != q.begin()) {
auto q1 = qit;
q1--;
if(sum - *q1 + *wit <= k) {
sum += *wit - *q1;
++cur;
--qit;
++wit;
reb = 1;
continue;
}
if(q1 != q.begin()){
auto q2 = q1;
q2--;
if(*q1 + *q2 > *wit) {
sum += *wit;
++wit;
sum -= *q1 + *q2;
--qit;
--qit;
reb = 1;
continue;
}
}
}
if(wit != w.begin() && qit != q.end()) {
auto q1 = qit;
auto w1 = wit;
w1--;
q1++;
if(q1 != q.end()) {
if(*qit + *q1 < *w1) {
reb = 1;
sum += *qit + *q1 - *w1;
wit--;
qit++;
qit++;
continue;
}
}
}
} while(reb);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
33864 KB |
Output is correct |
| 2 |
Correct |
132 ms |
39444 KB |
Output is correct |
| 3 |
Correct |
159 ms |
14776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12124 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12120 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
12124 KB |
1st lines differ - on the 1st token, expected: '30', found: '19' |
| 4 |
Halted |
0 ms |
0 KB |
- |
