#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick {
vector<ll> a;
int size;
int lg;
Fenwick(int size_) {
size = size_;
a.resize(size + 1, 0);
lg = 0;
while ((1 << lg) <= size) lg++;
}
void add(int i, ll v) {
for (; i <= size; i += i & -i) a[i] += v;
}
ll query(int i) {
ll ans = 0;
for (; i > 0; i -= i & -i) ans += a[i];
return ans;
}
int lower_bound(ll v) {
int idx = 0;
ll sum = 0;
for (int i = lg - 1; i >= 0; i--)
if (idx + (1 << i) <= size && sum + a[idx + (1 << i)] < v) {
idx += (1 << i);
sum += a[idx];
}
return idx + 1;
}
};
vector<ll> pval, qval;
vector<vector<tuple<int, int>>> gr;
vector<bool> inxy;
int N;
ll K;
void dfs(int p, int u, ll d, vector<ll> &dist, vector<int> &parent) {
parent[u] = p;
dist[u] = d;
for (auto &t : gr[u]) {
int v = get<0>(t);
if (v != p) dfs(u, v, d + get<1>(t), dist, parent);
}
}
int GetScoreWithoutCommon() {
vector<ll> pq;
pq.insert(pq.end(), pval.begin(), pval.end());
pq.insert(pq.end(), qval.begin(), qval.end());
sort(pq.begin(), pq.end());
ll total = 0;
int ans = 0;
for (ll c : pq) {
if (total + c <= K) {
total += c;
ans++;
} else
break;
}
return ans;
}
int GetScoreWithCommon() {
ll total_xy = 0;
int ans = 0;
for (int i = 0; i < N; i++)
if (inxy[i]) {
total_xy += pval[i];
qval[i] -= pval[i];
pval[i] = 0;
}
vector<tuple<ll, ll, int>> diffs;
for (int i = 0; i < N; i++) diffs.emplace_back(qval[i] - pval[i], pval[i], i);
sort(diffs.begin(), diffs.end());
vector<tuple<ll, int, int>> elem;
for (int i = 0; i < N; i++) {
elem.emplace_back(2 * pval[i], i, i);
elem.emplace_back(qval[i], -2 * i - 1, i);
elem.emplace_back(qval[i], -2 * i - 2, i);
}
elem.emplace_back(-1, 0, 0);
sort(elem.begin(), elem.end());
vector<int> pidx(N), qidx(N);
for (int i = 1; i < static_cast<int>(elem.size()); i++) {
int j = get<2>(elem[i]);
if (get<1>(elem[i]) >= 0)
pidx[j] = i;
else
qidx[j] = i;
}
Fenwick prefix(3 * N), p_ctr(3 * N), q_ctr(3 * N);
auto Knapsack01 = [&](ll cap) -> int {
int idx = prefix.lower_bound(cap + 1) - 1;
ll total = prefix.query(idx);
int score = p_ctr.query(idx) + q_ctr.query(idx);
if (q_ctr.query(idx) % 2 == 0) return score;
int curr_p = p_ctr.lower_bound(p_ctr.query(idx)),
curr_q = q_ctr.lower_bound(q_ctr.query(idx));
if (p_ctr.query(idx) != p_ctr.query(3 * N)) {
int next_p = p_ctr.lower_bound(p_ctr.query(idx) + 1);
if (total - get<0>(elem[curr_q]) + get<0>(elem[next_p]) <= cap)
return score;
}
if (curr_p > 0) {
if (total - get<0>(elem[curr_p]) + get<0>(elem[curr_q]) <= cap)
return score;
}
return score - 1;
};
for (int i = 0; i < N; i++) {
int idx = pidx[i];
prefix.add(idx, 2 * pval[i]);
p_ctr.add(idx, 1);
}
for (int i = 0; i < N; i++) {
int node = get<2>(diffs[i]);
int idx = pidx[node];
prefix.add(idx, -2 * pval[node]);
p_ctr.add(idx, -1);
idx = qidx[node];
prefix.add(idx, qval[node]);
prefix.add(idx - 1, qval[node]);
q_ctr.add(idx, 1);
q_ctr.add(idx - 1, 1);
if (total_xy <= K) {
int score = Knapsack01(2 * (K - total_xy));
ans = max(ans, score);
}
}
return ans;
}
int max_score(int N_, int X, int Y, long long K_, vector<int> U, vector<int> V,
vector<int> W) {
N = N_;
K = K_;
gr.assign(N, vector<tuple<int, int>>());
pval.resize(N);
qval.resize(N);
inxy.assign(N, false);
vector<int> parent(N);
for (int i = 0; i < static_cast<int>(U.size()); i++) {
gr[U[i]].emplace_back(V[i], W[i]);
gr[V[i]].emplace_back(U[i], W[i]);
}
dfs(-1, X, 0, pval, parent);
dfs(-1, Y, 0, qval, parent);
for (int i = 0; i < N; i++) {
ll t = min(pval[i], qval[i]);
qval[i] = max(pval[i], qval[i]);
pval[i] = t;
}
for (int u = X; u != -1; u = parent[u]) inxy[u] = true;
return max(GetScoreWithoutCommon(), GetScoreWithCommon());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
62140 KB |
1st lines differ - on the 1st token, expected: '451', found: '69008' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '34', found: '39' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '34', found: '39' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '34', found: '39' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
2nd lines differ - on the 1st token, expected: '3', found: '6' |
| 2 |
Halted |
0 ms |
0 KB |
- |
