#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
vector<vector<array<int, 2>>> g(N);
vector c(2, vector<ll>(N));
vector<int> par(N);
for(int i=0; i<N-1; i++){
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
function<void(int, int, vector<ll>&)> dfs = [&](int u, int p, vector<ll> &c){
par[u] = p;
for(auto [v, cost]:g[u]){
if(v==p){
continue;
}
c[v]+=c[u] + cost;
dfs(v, u, c);
}
};
dfs(X, -1, c[0]);
dfs(Y, -1, c[1]);
auto get = [&](ll K){
int ans = 0;
vector vis(2, vector<int>(N));
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
// (cost, node, start x or y)
pq.push({0, X, 0});
pq.push({0, Y, 1});
while(pq.size()){
auto [cost, u, start] = pq.top();
pq.pop();
if(vis[start][u]){
continue;
}
vis[start][u]=1;
if(K<cost){
break;
}
//cerr << u << " " << cost << " " << start << endl;
ans++;
K-=cost;
for(auto [v, _]:g[u]){
pq.push({c[start][v], v, start});
}
}
return ans;
};
auto get2 = [&](ll K){
int ans = 0;
vector vis(2, vector<int>(N));
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pq2;
auto getnext = [&](auto u, auto start){
array<ll, 3> best = {ll(1e9)};
for(auto [v, _]:g[u]){
if(vis[start^1][v] and c[start^1][v] <= c[start][v]){
if(not vis[start][v])
best = min(best, {c[start][v] - c[start^1][v], v, start});
}else{
if(not vis[start][v])
best = min(best, {c[start][v], v, start});
}
}
return best;
};
auto visite = [&](auto u, auto start, ll cost){
vis[start][u]=1;
if(cost>K) return;
cerr << u << " " << start << " " << cost << " " << K << endl;
K -= cost;
ans++;
for(auto [v, _]:g[u]){
if(vis[start^1][v] and c[start^1][v] <= c[start][v]){
pq.push({c[start][v] - c[start^1][v], v, start});
}else{
pq.push({c[start][v], v, start});
}
if(vis[start^1][v] and c[start^1][u] >= c[start][u]){
pq.push({c[start^1][u] - c[start][u], u, start^1});
}
if(vis[start^1][u]){
pq2.push({2 * max(c[0][v], c[1][v]) - min(c[0][v], c[1][v]), v});
}
}
};
for(int u=X; ; u=par[u]){
if(min(c[0][u], c[1][u])>K){
return ans;
}
if(c[0][u]<c[1][u]){
visite(u, 0, c[0][u]);
}else{
visite(u, 1, c[1][u]);
}
if(u==Y) break;
}
cerr << K << endl;
cerr << ans << endl;
while(pq.size() or pq2.size()){
vector<array<ll, 3>> todo;
array<ll, 2> cur = {-1, -1};
while(pq.size() and todo.size()<2){
auto [cost, u, start] = pq.top();
pq.pop();
if(vis[start][u]){
continue;
}
todo.push_back({cost, u, start});
}
while(pq2.size() and cur[0]==-1){
auto [cost, u]=pq2.top();
pq2.pop();
if(vis[0][u] or vis[1][u]) continue;
cur = {cost, u};
}
// todo.size() == 1
// todo.size() == 0
// todo.size() == 2
if(todo.size()==0 and cur[0]!=-1 and K>=cur[0]){
visite(cur[1], 0, cur[0]);
visite(cur[1], 1, 0);
}if(todo.size()==1){
if(cur[0]==-1){
visite(todo[0][1], todo[0][2], todo[0][0]);
}else{
auto v = getnext(todo[0][1], todo[0][2]);
if(todo[0][0] + v[0] < cur[0]){
visite(todo[0][1], todo[0][2], todo[0][0]);
pq2.push(cur);
}else{
visite(cur[1], 0, cur[0]);
visite(cur[1], 1, 0);
pq.push(todo[0]);
}
}
}if(todo.size()==2){
if(cur[0]==-1){
visite(todo[0][1], todo[0][2], todo[0][0]);
pq.push(todo[1]);
}else{
auto v = getnext(todo[0][1], todo[0][2]);
if(todo[0][0] + min(v[0], todo[1][0]) < cur[0]){
visite(todo[0][1], todo[0][2], todo[0][0]);
pq.push(todo[1]);
pq2.push(cur);
}else{
visite(cur[1], 0, cur[0]);
visite(cur[1], 1, 0);
pq.push(todo[0]);
pq.push(todo[1]);
}
}
}
}
return ans;
};
return max(get(K), get2(K));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
29748 KB |
Output is correct |
| 2 |
Correct |
90 ms |
40380 KB |
Output is correct |
| 3 |
Correct |
82 ms |
5592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
1st lines differ - on the 1st token, expected: '30', found: '34' |
| 4 |
Halted |
0 ms |
0 KB |
- |
