#include <bits/stdc++.h>
#include "closing.h"
using namespace std;
#define ff first
#define ss second
#define pii pair<int, int>
using ll = long long;
vector<ll> c;
vector<vector<pii>> E;
bool dfs(int x, int p, ll sm, int t) {
if (x == t) {
c[x] = max(c[x], sm);
return true;
}
for (auto [i, w] : E[x]) {
if (i == p) continue;
if (dfs(i, x, sm + w, t)) {
c[x] = max(c[x], sm);
return true;
}
}
return false;
}
int max_score(int n, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
E.assign(n, {});
for (int i = 0; i < n - 1; i++) {
E[U[i]].push_back({V[i], W[i]});
E[V[i]].push_back({U[i], W[i]});
}
auto f = [&](int st) -> vector<ll> {
queue<int> q;
vector<ll> dis(n, -1);
q.push(st); dis[st] = 0;
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto [i, w] : E[x]) {
if (dis[i] == -1) {
dis[i] = dis[x] + w;
q.push(i);
}
}
}
return dis;
};
vector<ll> disx = f(X), disy = f(Y);
if (n <= 20) {
int mx = 0;
for (int mk = 0; mk < (1 << n); mk++) {
c.assign(n, -1);
for (int i = 0; i < n; i++) {
if (!((mk >> i) & 1)) continue;
dfs(X, -1, 0, i); dfs(Y, -1, 0, i);
}
ll sm = 0;
for (auto i : c)
if (i != -1) sm += i;
if (sm > K) continue;
vector<int> u;
for (int i = 0; i < n; i++) {
if (c[i] == -1) u.push_back(min(disx[i], disy[i]));
}
sort(u.begin(), u.end());
int cnt = 0;
for (int i = 0; i < n; i++) {
if (c[i] != -1) cnt += 1 + (c[i] != min(disx[i], disy[i]));
}
int z = cnt;
for (auto i : u) {
if (sm + i <= K) {
sm += i;
cnt++;
}
else break;
}
mx = max(mx, cnt);
}
return mx;
}
vector<pii> v;
for (int i = 0; i < n; i++) {
if ((int)E[i].size() == 1) {
v.push_back({i, 0});
queue<int> q;
vector<bool> vis(n);
q.push(i); vis[i] = true;
while (!q.empty()) {
auto x = q.front(); q.pop();
for (auto [j, w] : E[x]) {
if (!vis[j]) {
q.push(j);
vis[j] = true;
v.push_back({j, w});
}
}
}
break;
}
}
for (auto [i, w] : v) {
if (i == X || i == Y) {
if (i == Y) swap(X, Y);
break;
}
}
int a = -1, b = -1;
for (int i = 0; i < (int)v.size(); i++) {
if (v[i].ff == X) a = i;
else if (v[i].ff == Y) b = i;
}
vector<int> u;
for (int k = 0; k < n; k++) {
u.push_back(min(disx[v[k].ff], disy[v[k].ff]));
}
sort(u.begin(), u.end());
ll sm = 0;
int cnt = 0;
for (auto i : u) {
if (sm + i <= K) {
sm += i;
cnt++;
}
else break;
}
int mx = cnt;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
vector<ll> c(n, -1);
for (auto x : {a, b}) {
for (auto y : {i, j}) {
ll sm = 0;
c[x] = max(c[x], 0LL);
if (y <= x) {
for (int k = x - 1; k >= y; k--)
c[k] = max(c[k], sm += v[k + 1].ss);
}
else {
for (int k = x + 1; k <= y; k++)
c[k] = max(c[k], sm += v[k].ss);
}
}
}
ll sm = 0;
for (auto k : c)
if (k != -1) sm += k;
if (sm > K) break;
vector<int> u;
for (int k = 0; k < n; k++) {
if (c[k] == -1) u.push_back(min(disx[v[k].ff], disy[v[k].ff]));
}
sort(u.begin(), u.end());
int cnt = 0;
for (int i = 0; i < n; i++) {
if (c[i] != -1) cnt += 1 + (c[i] != min(disx[i], disy[i]));
}
for (auto i : u) {
if (sm + i <= K) {
sm += i;
cnt++;
}
else break;
}
mx = max(mx, cnt);
}
}
return mx;
}
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:87:17: warning: unused variable 'z' [-Wunused-variable]
87 | int z = cnt;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1065 ms |
25284 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Execution timed out |
1087 ms |
348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
