#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6e3 + 5;
const long long INF = 1e18;
int onp[maxn];
long long depX[maxn], depY[maxn];
vector<pair<int, int>> g[maxn];
void dfsX(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depX[v.first] = depX[x] + v.second;
dfsX(v.first, x);
}
}
void dfsY(int x, int p = -1)
{
for (auto v : g[x])
{
if (v.first == p)
continue;
depY[v.first] = depY[x] + v.second;
dfsY(v.first, x);
}
}
long long solve1(int n, long long k)
{
vector<long long> vec;
vec.insert(vec.end(), depX, depX + n);
vec.insert(vec.end(), depY, depY + n);
sort(vec.begin(), vec.end());
long long crr = 0;
for (int i = 0; i < vec.size(); i++)
{
crr += vec[i];
if (crr > k)
return i;
}
return vec.size();
}
vector<int> path;
bool dfs_path(int x, int endp, int p = -1)
{
if (x == endp)
return (onp[x] = true);
for (auto v : g[x])
{
if (v.first == p)
continue;
onp[x] |= dfs_path(v.first, endp, x);
}
return onp[x];
}
vector<long long> vec1, vec2;
vector<long long> knapsack[maxn];
int mark[maxn];
bool chk(pair<int, int> a)
{
return a.second < mark[a.first];
}
long long tval(pair<int, int> a)
{
if (chk(a))
return knapsack[a.first][a.second];
else
return knapsack[a.first][a.second] + knapsack[a.first][a.second + 1];
}
long long eval(pair<int, int> a)
{
if (chk(a))
return knapsack[a.first][a.second] * 2;
else
return knapsack[a.first][a.second] + knapsack[a.first][a.second + 1];
}
struct cmp
{
bool operator()(const pair<int, int> a, const pair<int, int> b) const
{
return eval(a) > eval(b);
}
};
long long brute(priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq, pair<int, int> val, long long k) {
auto old_pq = pq;
long long ans1 = 0, ans2 = 0, old_k = k;
while(!pq.empty()){
auto x = pq.top();
pq.pop();
if(k >= tval(x))k-=tval(x);
else break;
ans1+=2;
}
pq = old_pq;
k = old_k;
if(k >= tval(val)){
k -= tval(val);
ans2++;
for(int i = mark[val.first]; i < knapsack[val.first].size(); i+=2) {
pq.push({val.first, i});
}
while(!pq.empty()){
auto x = pq.top();
pq.pop();
if(k >= tval(x))k-=tval(x);
else break;
ans2+=2;
}
}
return max(ans1, ans2);
}
void dfs_gen(int x, int p, long long cnst)
{
long long val;
if (p == -1)
val = 0;
else
val = min(depX[x], depY[x]);
if (val > cnst)
vec2.push_back(val);
else
vec1.push_back(val);
for (auto v : g[x])
{
if (v.first == p || onp[v.first])
continue;
dfs_gen(v.first, x, cnst);
}
}
long long solve2(int n, long long k, int x, int y)
{
dfs_path(x, y);
int len = 0;
for (int i = 0; i < n; i++)
{
if (onp[i])
{
k -= min(depX[i], depY[i]);
vec1.clear();
vec2.clear();
long long inc = abs(depX[i] - depY[i]);
dfs_gen(i, -1, inc);
sort(vec1.begin(), vec1.end());
sort(vec2.begin(), vec2.end());
knapsack[len] = vec1;
for (auto v : vec1)
knapsack[len].push_back(inc);
mark[len] = knapsack[len].size();
for (auto v : vec2)
{
knapsack[len].push_back(v);
knapsack[len].push_back(inc);
}
len++;
// cout << i << endl;
// for(auto v: knapsack[len])cout << v << " ";
// cout << endl;
}
}
// cout << "left " << k << endl;
if (k < 0)
return 0;
long long re = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq1;
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq2;
for (int i = 0; i < len; i++){
for(int j = 0; j < mark[i]; j++)pq1.push({i, j});
}
while(!pq1.empty() || !pq2.empty()) {
if(pq1.empty()){
auto x = pq2.top();
pq2.pop();
if(k >= tval(x))k -= tval(x);
else {
if(k >= knapsack[x.first][x.second]){
re++;
}
break;
}
re += 2;
}
else if(pq2.empty()){
auto x = pq1.top();
pq1.pop();
if(k >= tval(x))k -= tval(x);
else break;
re++;
}
else {
auto pval = pq2.top();
pq2.pop();
auto val1 = pq1.top();
pq1.pop();
if(pq1.empty()){
return re + brute(pq1, val1, k);
}
else {
auto val2 = pq1.top();
pq1.pop();
if(tval(pval) < tval(val1) + tval(val2)){
if(k >= tval(pval)){
pq1.push(val1);
pq1.push(val2);
re += 2;
}
else {
if(k >= knapsack[pval.first][pval.second] + tval(val1))re += 2;
else if(k >= min(knapsack[pval.first][pval.second], tval(val1)))re++;
break;
}
}
else {
if(k >= tval(val1) + tval(val2)){
if(val1.second + 1 == mark[val1.first]){
for(int i = mark[val1.first]; i < knapsack[val1.first].size(); i+=2)pq2.push({val1.first, i});
}
if(val2.second + 1 == mark[val2.first]){
for(int i = mark[val2.first]; i < knapsack[val2.first].size(); i+=2)pq2.push({val2.first, i});
}
pq2.push(pval);
}
else {
if(k >= knapsack[pval.first][pval.second] + tval(val1))re += 2;
else if(k >= min(knapsack[pval.first][pval.second], tval(val1)))re++;
break;
}
}
}
}
}
return re;
}
void reset(int n)
{
for (int i = 0; i < n; i++)
{
g[i].clear();
onp[i] = 0;
}
path.clear();
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
reset(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]});
}
depX[X] = 0;
depY[Y] = 0;
dfsX(X);
dfsY(Y);
long long ans = max(solve1(N, K), solve2(N, K, X, Y));
return ans;
}
Compilation message
closing.cpp: In function 'long long int solve1(int, long long int)':
closing.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < vec.size(); i++)
| ~~^~~~~~~~~~~~
closing.cpp: In function 'long long int brute(std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, cmp>, std::pair<int, int>, long long int)':
closing.cpp:114:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i = mark[val.first]; i < knapsack[val.first].size(); i+=2) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
closing.cpp: In function 'long long int solve2(int, long long int, int, int)':
closing.cpp:165:23: warning: unused variable 'v' [-Wunused-variable]
165 | for (auto v : vec1)
| ^
closing.cpp:234:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
234 | for(int i = mark[val1.first]; i < knapsack[val1.first].size(); i+=2)pq2.push({val1.first, i});
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
closing.cpp:237:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
237 | for(int i = mark[val2.first]; i < knapsack[val2.first].size(); i+=2)pq2.push({val2.first, i});
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
10492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
596 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
596 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
596 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
596 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
596 KB |
Output is correct |
| 2 |
Correct |
0 ms |
596 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
596 KB |
1st lines differ - on the 1st token, expected: '30', found: '24' |
| 4 |
Halted |
0 ms |
0 KB |
- |
