#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int max_score(int N, int X, int Y, long long K,
vector<int> U, vector<int> V, vector<int> W) {
vector <pair<int, int>> adj[N];
vector <vector<int>> adj1[2];
adj1[0] = vector < vector < int >> (N);
adj1[1] = vector < vector < int >> (N);
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]});
}
vector <ll> D[2];
D[0] = vector<ll>(N);
D[1] = vector<ll>(N);
int XY[2] = {X, Y};
vector<int> x2y;
for (int t: {0, 1}) {
D[t][XY[t]] = 0;
vector<int> P;
function<void(int, int)> dfs = [&](int i, int p) -> void {
if (p != -1) {
adj1[t][p].push_back(i);
}
P.push_back(i);
if (t == 0 && i == Y) {
x2y = P;
}
for (auto j: adj[i]) {
if (j.first == p) {
continue;
}
D[t][j.first] = D[t][i] + j.second;
dfs(j.first, i);
}
P.pop_back();
};
dfs(XY[t], -1);
}
int ret = 0;
vector <ll> cost[2];
for (int t: {0, 1}) {
ll sum = 0;
priority_queue <pair<int, int>> Q;
Q.push({0, XY[t]});
while (!Q.empty()) {
int i = Q.top().second;
Q.pop();
sum += D[t][i];
cost[t].push_back(sum);
if (sum > K) {
break;
}
for (auto j: adj1[t][i]) {
Q.push({-D[t][j], j});
}
}
}
for (int i = 0; i < cost[0].size(); i++) {
for (int j = 0; j < cost[1].size(); j++) {
if (cost[0][i] + cost[1][j] <= K) {
ret = max(ret, i + 1 + j + 1);
}
}
}
int m = 0;
while (m + 1 < x2y.size() && D[0][x2y[m + 1]] <= D[1][x2y[m + 1]]) {
m++;
}
ll s0 = 0;
ll s1 = 0;
for (int i = 0; i <= m; i++) {
s0 += D[0][x2y[i]];
s0 = min(s0, K + 1);
}
for (int j = x2y.size() - 1; j > m; j--) {
s1 += D[1][x2y[j]];
s1 = min(s1, K + 1);
}
if (s0 + s1 > K) {
return ret;
}
K -= s0 + s1;
bool free[N];
for (int i: x2y) {
free[i] = true;
}
auto merge = [&](const vector <ll> &a, const vector <ll> &b) {
vector <ll> r(a.size() + b.size() - 1, K + 1);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
r[i + j] = min(r[i + j], a[i] + b[j]);
}
}
return r;
};
function < array < vector < ll > , 2 > (int, int, int) > fn = [&](int t, int i, int p) -> array<vector<ll>, 2> {
vector <ll> ch[2] = {{0},
{0}};
for (auto j: adj[i]) {
if (j.first == p) {
continue;
}
auto arrs = fn(t, j.first, i);
ch[0] = merge(ch[0], arrs[0]);
ch[1] = merge(ch[1], arrs[1]);
}
ll buyX = D[t][i];
ll buyY = D[1 - t][i];
if (free[i]) {
buyX = 0;
buyY -= D[t][i];
}
array<vector<ll>, 2> ret;
ret[0] = {0};
ret[1] = {0};
for (int i = 0; i < ch[0].size(); i++) {
if (i + 1 >= ret[0].size()) {
ret[0].push_back(K + 1);
}
if (i + 1 >= ret[1].size()) {
ret[1].push_back(K + 1);
}
ret[0][i + 1] = min(ret[0][i + 1], ch[0][i] + buyX);
ret[1][i + 1] = min(ret[1][i + 1], ch[0][i] + buyX);
}
for (int i = 0; i < ch[1].size(); i++) {
if (i + 1 >= ret[1].size()) {
ret[1].push_back(K + 1);
}
ret[1][i + 1] = min(ret[1][i + 1], ch[1][i] + buyY);
}
return ret;
};
auto cost0 = fn(0, x2y[m], x2y[m + 1])[1];
auto cost1 = fn(1, x2y[m + 1], x2y[m])[1];
auto ans = merge(cost0, cost1);
for (int i = 0; i < ans.size(); i++) {
if (ans[i] <= K) {
ret = max(ret, i + int(x2y.size()));
}
}
return ret;
}
Compilation message
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for (int i = 0; i < cost[0].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
closing.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int j = 0; j < cost[1].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
closing.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | while (m + 1 < x2y.size() && D[0][x2y[m + 1]] <= D[1][x2y[m + 1]]) {
| ~~~~~~^~~~~~~~~~~~
closing.cpp: In lambda function:
closing.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
closing.cpp:99:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for (int j = 0; j < b.size(); j++) {
| ~~^~~~~~~~~~
closing.cpp: In lambda function:
closing.cpp:126:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i = 0; i < ch[0].size(); i++) {
| ~~^~~~~~~~~~~~~~
closing.cpp:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if (i + 1 >= ret[0].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~
closing.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | if (i + 1 >= ret[1].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~
closing.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for (int i = 0; i < ch[1].size(); i++) {
| ~~^~~~~~~~~~~~~~
closing.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | if (i + 1 >= ret[1].size()) {
| ~~~~~~^~~~~~~~~~~~~~~~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:148:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for (int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
188 ms |
44580 KB |
Output is correct |
| 2 |
Correct |
187 ms |
55688 KB |
Output is correct |
| 3 |
Correct |
83 ms |
3056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '10' |
| 2 |
Halted |
0 ms |
0 KB |
- |
