#include<bits/stdc++.h>
#include "closing.h"
#define fi first
#define se second
#define ll long long
using namespace std;
const ll N = 2e5 + 10;
bitset<N> us;
vector<pair<ll, ll>> gr[N];
ll dist[N][2];
ll ds[N][2];
bool flag;
void ultra_clear(ll n) {
flag &= 0;
for (ll i = 0; i < n; ++i) {
for (ll j = 0; j < 2; ++j)
dist[i][j] &= 0,
ds[i][j] &= 0;
gr[i].clear();
us[i] = 0;
}
}
void pre_calc(ll city, ll last, ll type) {
for (auto i : gr[city]) {
if (i.fi == last)
continue;
dist[i.fi][type] = dist[city][type] + i.se;
pre_calc(i.fi, city, type);
}
}
void get_path(ll city, ll last, ll y, vector<ll> &path) {
if (!flag)
path.push_back(city);
if (city == y) {
flag = 1;
return;
}
for (auto i : gr[city]) {
if (i.fi == last)
continue;
get_path(i.fi, city, y, path);
}
if (!flag)
path.pop_back();
}
int max_score(int n, int x, int y, ll k, vector<int> u, vector<int> v, vector<int> w) {
ultra_clear(n);
int m = n - 1, ans = 0;
for (ll i = 0; i < m; ++i) {
gr[u[i]].push_back({v[i], w[i]});
gr[v[i]].push_back({u[i], w[i]});
}
dist[x][0] = dist[y][1] &= 0;
pre_calc(x, 0, 0);
pre_calc(y, 0, 1);
set<pair<ll, ll>> stx, sty;
vector<ll> path;
get_path(x, 0, y, path);
ll psz = path.size() - 1;
for (ll i = 0; i <= path.size(); ++i) {
for (ll j = 0; j <= path.size(); ++j) {
ll hp = k;
ll cnt = 0;
ll now[n] = {};
bool us[n][2] = {};
for (ll q = 0; q < n; ++q)
ds[q][0] = dist[q][0],
ds[q][1] = dist[q][1];
for (ll q = 0; q < i - 1; ++q)
now[path[q]] = max(now[path[q]], dist[path[q]][0]);
for (ll q = 0; q < j - 1; ++q)
now[path[psz - q]] = max(now[path[psz - q]], dist[path[psz - q]][1]);
for (ll q = 0; q <= psz; ++q) {
for (ll z = 0; z < 2; ++z)
ds[path[q]][z] = max(0ll, ds[path[q]][z] - now[path[q]]);
hp -= now[path[q]];
}
if (hp < 0)
break;
set<pair<ll, ll>> stx, sty;
for (ll i = 0; i < n; ++i)
stx.insert({ds[i][0], i}),
sty.insert({ds[i][1], i});
// cout << "abu\n";
// cout << "i = " << i << ' ' << "j = " << j <<'\n';
while (stx.size() || sty.size()) {
pair<ll, ll> p1 = {1e18 + 1, 1e18}, p2 = {1e18 + 1, 1e18};
if (stx.size())
p1 = *stx.begin();
if (sty.size())
p2 = *sty.begin();
// cout << hp << ' ' << p1.fi << ' ' << p1.se << ' ' << p2.fi << ' ' << p2.se << '\n';
if (p1.fi <= p2.fi) {
if (hp - p1.fi < 0)
break;
hp -= p1.fi;
us[p1.se][0] = 1;
if (!us[p1.se][1])
sty.erase({max(0ll, dist[p1.se][1] - now[p1.se]), p1.se});
now[p1.se] += p1.fi;
if (!us[p1.se][1])
sty.insert({max(0ll, dist[p1.se][1] - now[p1.se]), p1.se});
stx.erase(stx.begin());
} else {
if (hp - p2.fi < 0)
break;
us[p2.se][1] = 1;
hp -= p2.fi;
if (!us[p2.se][0])
stx.erase({max(0ll, dist[p2.se][0] - now[p2.se]), p2.se});
now[p2.se] += p2.fi;
if (!us[p2.se][0])
stx.insert({max(0ll, dist[p2.se][0] - now[p2.se]), p2.se});
sty.erase(sty.begin());
}
++cnt;
}
ans = max((ll)ans, cnt);
}
}
return ans;
}
//signed main() {
//// ios::sync_with_stdio(0);
//// cin.tie(0); cout.tie(0);
// int t;
// cin >> t;
// while (t--) {
// int n;
// int x, y;
// ll k;
// cin >> n >> x >> y >> k;
// vector<int> u(n - 1), v(n - 1), w(n - 1);
// for (int i = 0; i < n - 1; ++i)
// cin >> u[i] >> v[i] >> w[i];
// cout << max_score(n, x, y, k, u, v, w);
// }
// return 0;
//}
//2
//7 0 2 10
//0 1 2
//0 3 3
//1 2 4
//2 4 2
//2 5 5
//5 6 3
//4 0 3 20
//0 1 18
//1 2 1
//2 3 19
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:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for (ll i = 0; i <= path.size(); ++i) {
| ~~^~~~~~~~~~~~~~
closing.cpp:61:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (ll j = 0; j <= path.size(); ++j) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9052 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
57552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9048 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9048 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9048 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9052 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9052 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9052 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9052 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9052 KB |
2nd lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
