#include <bits/stdc++.h>
#define int long long
using namespace std;
int z[400005];
struct node {
int a, b;
bool operator < (const node &z) const {
return b < z.b;
}
} c[400005];
namespace Cardboard_Box {
int cnt, p[400005], q[400005];
int d[400005], nu[400005], su[400005];
void add (int x, int v1, int v2) {
while (x <= cnt) {
nu[x] += v1, su[x] += v2;
x += x & -x;
}
}
int solve (int n, int K, node *c, int m, int *z) {
cnt = 0;
for (int i = 1; i <= m; i++) d[++cnt] = z[i];
for (int i = 1; i <= n; i++) {
d[++cnt] = c[i].a;
d[++cnt] = c[i].b - c[i].a;
}
sort (c + 1, c + n + 1);
sort (d + 1, d + cnt + 1);
cnt = unique (d + 1, d + cnt + 1) - d - 1;
int sum = 0;
memset (nu, 0, cnt + 2 << 3);
memset (su, 0, cnt + 2 << 3);
for (int i = 1; i <= m; i++) {
int pos = lower_bound (d + 1, d + cnt + 1, z[i]) - d;
add (pos, 1, z[i]);
}
for (int i = 1; i <= n; i++) {
p[i] = lower_bound (d + 1, d + cnt + 1, c[i].a) - d;
q[i] = lower_bound (d + 1, d + cnt + 1, c[i].b - c[i].a) - d;
add (p[i], 1, c[i].a);
}
int ans = 0;
for (int i = 0; i <= n; i++) {
if (i) {
add (p[i], -1, -c[i].a);
add (q[i], 1, c[i].b - c[i].a);
K -= c[i].a;
}
if (K < 0) break;
int p = 0, num = 0, sum = 0;
for (int j = __lg (cnt); j >= 0; j--) {
int np = p + (1 << j);
if (np > cnt || sum + su[np] > K) continue;
p = np, num += nu[p], sum += su[p];
}
if (p < cnt) num += (K - sum) / d[p + 1];
ans = max (ans, num + i);
}
return ans;
}
}
int dx[400005], dy[400005];
vector<pair <int, int>> e[400005];
void dfs (int x, int fl, int *d) {
if (fl == -1) d[x] = 0;
for (pair <int, int> t : e[x]) {
int it = t.first;
if (it == fl) continue;
d[it] = d[x] + t.second;
dfs (it, x, d);
}
}
int max_score (int N, int X, int Y, int K, vector<int> U, vector<int> V, vector<int> W) {
for (int i = 0; i < N; i++) e[i].clear();
for (int i = 0; i + 1 < N; i++) {
e[U[i]].push_back ({V[i], W[i]});
e[V[i]].push_back ({U[i], W[i]});
}
dfs (X, -1, dx), dfs (Y, -1, dy);
vector<int> arr;
for (int i = 0; i < N; i++) {
arr.push_back (dx[i]);
arr.push_back (dy[i]);
}
sort (arr.begin(), arr.end());
int ans = 0;
int sum = 0;
for (int i = 0; i < (int)arr.size(); i++) {
if ((sum += arr[i]) > K) break;
ans++;
}
int n = 0, m = 0, cnt = 0;
for (int i = 0; i < N; i++) {
int mn = min (dx[i], dy[i]);
int mx = max (dx[i], dy[i]);
if (dx[i] + dy[i] == dx[Y]) {
cnt++, K -= mn;
z[++ m] = mx - mn;
}
else c[++ n] = {mn, mx};
}
if (K >= 0) ans = max (ans, cnt + Cardboard_Box::solve (n, K, c, m, z));
return ans;
}
Compilation message
closing.cpp: In function 'long long int Cardboard_Box::solve(long long int, long long int, node*, long long int, long long int*)':
closing.cpp:31:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
31 | memset (nu, 0, cnt + 2 << 3);
| ~~~~^~~
closing.cpp:32:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
32 | memset (su, 0, cnt + 2 << 3);
| ~~~~^~~
closing.cpp:30:7: warning: unused variable 'sum' [-Wunused-variable]
30 | int sum = 0;
| ^~~
/usr/bin/ld: /tmp/ccuhxt7m.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
