#include "closing.h"
// #pragma optimize ("O3")
// #pragma target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 3e5+10;
const ll INF = 1e18;
int sz[N];
vector<pair<int, ll>> g[N];
ll val1[N], val2[N], T[N][2];
void build(int l, int r, int k){
if(l == r){
T[k][0] = 0;
T[k][1] = 0;
return;
}
int m = l+r>>1;
build(l, m, k<<1);
build(m+1, r, k<<1|1);
T[k][0] = 0;
T[k][1] = 0;
}
void upd(int l, int r, int p, int k, ll val, int co){
if(l == r){
T[k][0] = val;
T[k][1] = co;
return;
}
int m = l+r>>1;
if(p <= m) upd(l, m, p, k<<1, val, co);
else upd(m+1, r, p, k<<1|1, val, co);
T[k][0] = T[k<<1][0] + T[k<<1|1][0];
T[k][1] = T[k<<1][1] + T[k<<1|1][1];
}
pair<ll, ll> get(int l, int r, int k, ll R){
if(R >= T[k][0]) return {T[k][0], T[k][1]};
if(l == r){
return {0ll, 0ll};
}
int m = l+r>>1;
pair<ll, ll> ans = {0ll, 0ll};
if(T[k<<1][0] <= R){
ans = get(l, m, k<<1, R);
}else{
return get(l, m, k<<1, R);
}
R -= ans.ff;
auto x = get(m+1, r, k<<1|1, R);
return {x.ff + ans.ff, x.ss + ans.ss};
}
void dfs(int v, int p, vector<ll> &D){
for(auto U: g[v]){
int u = U.ff;
if(u != p){
D[u] = D[v] + U.ss;
dfs(u, v, D);
}
}
}
vector<int> euler;
bool pre(int v, int p, int t){
euler.pb(v);
if(v == t){
return 1;
}
for(auto U: g[v]){
int u = U.ff;
if(u != p){
bool ok = pre(u, v, t);
if(ok) return 1;
}
}
euler.pop_back();
return 0;
}
int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){
for(int i = 0; i < n; ++i) g[i].clear();
euler.clear();
for(int i = 0; i < n - 1; ++i){
g[V[i]].pb({U[i], W[i]});
g[U[i]].pb({V[i], W[i]});
}
if(X > Y) swap(X,Y);
vector<ll> D1(n), D2(n);
dfs(X, X, D1);
dfs(Y, Y, D2);
vector<ll> A;
for(int i =0 ; i < n; ++i) A.pb(D1[i]);
for(int i =0 ; i < n; ++i) A.pb(D2[i]);
sort(all(A));
int anss = 0; ll tot = 0;
for(int i = 0; i < A.size(); ++i){
if(tot + A[i] <= K) tot += A[i], ++anss;
}
pre(X, X, Y);
vector<bool> s(n);
for(int v: euler) s[v] = 1;
vector<array<ll, 3>> vals;
for(int i = 0; i < n; ++i){
if(s[i]){
val1[i] = max(D1[i], D2[i]) - min(D1[i], D2[i]);
val2[i] = -1;
K -= min(D1[i], D2[i]);
vals.pb({2*val1[i], i, 4});
}else{
val1[i] = min(D1[i], D2[i]);
val2[i] = max(D1[i], D2[i]) - val1[i];
vals.pb({2*val1[i], i, 1});
if(val2[i] < val1[i]){
vals.pb({val1[i]+val2[i], i, 3});
}else{
vals.pb({2*val2[i], i, 2});
}
}
}
if(K<0) return anss;
// cout << K << ' ';
sort(all(vals));
vector<int> used(n);
int d = vals.size();
build(0, d-1, 1);
for(int i = 0; i < vals.size(); ++i){
int idx = vals[i][1];
int co = vals[i][2];
if(co == 3){
upd(0, d-1, i, 1, vals[i][0], 2);
used[idx] = 1;
}else if(co == 4){
upd(0, d-1, i, 1, vals[i][0] / 2, 1);
}else if(co == 2 || (co == 1 && !used[idx])){
upd(0, d-1, i, 1, vals[i][0] / 2, 1);
}else if(co == 1 && used[idx]){
used[idx] = i;
}
}
int best = get(0, d-1, 1, K).ss;
for(int i = 0; i < vals.size(); ++i){
int idx = vals[i][1];
int co = vals[i][2];
if(co == 3){
upd(0, d-1, i, 1, 0, 0);
// upd(0, d-1, used[idx], 1, val1[idx], 1);
if(K >= vals[idx][0] / 2){
best = max(best, (int)get(0, d-1, 1, K - vals[idx][0] / 2).ss + 1);
// cout << idx << '\n';
}
upd(0, d-1, i, 1, vals[i][0], 2);
}
}
// for(int i = 0; i < n; ++i){
// cout << val1[i] << ' ' << val2[i] << '\n';
// }
return max(best+int(euler.size()), anss);
// for(int v: euler){
// p(v, v);
// calc(v, v);
// }
// for(int u: euler){
// for(int j = 2; j <= sz[u]; ++j){
// assert(dp[u][j] - dp[u][j - 1] >= dp[u][j - 1] - dp[u][j - 2]);
// }
// }
// int ans = 0;
// ll ls = 0, rs = 1e18;
// while(ls <= rs){
// ll lm = ls+rs>>1;
// int num = 0;
// ll cost = 0;
// for(int u: euler){
// for(int j = 1; j <= sz[u]; ++j){
// if(dp[u][j] - dp[u][j - 1] <= lm){
// cost += dp[u][j] - dp[u][j - 1];
// ++num;
// if(cost <= K){
// ans = max(ans, num);
// }
// }
// }
// }
// if(cost > K){
// rs = lm - 1;
// }else{
// ls = lm + 1;
// }
// }
// vector<ll> DP(2*n + 5, INF);
// DP[0] = 0;
// int S = 0;
// for(int u: euler){
// S += sz[u];
// for(int j = S; j >= 1; --j){
// for(int l = 1; l <= min(sz[u], j); ++l){
// DP[j] = min(DP[j], DP[j - l] + dp[u][l]);
// }
// }
// }
// for(int i = 2*n; i >= 0; --i){
// if(DP[i] <= K){
// }
// }
// return anss;
}
Compilation message
closing.cpp: In function 'void build(int, int, int)':
closing.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int m = l+r>>1;
| ~^~
closing.cpp: In function 'void upd(int, int, int, int, long long int, int)':
closing.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = l+r>>1;
| ~^~
closing.cpp: In function 'std::pair<long long int, long long int> get(int, int, int, long long int)':
closing.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int m = l+r>>1;
| ~^~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for(int i = 0; i < A.size(); ++i){
| ~~^~~~~~~~~~
closing.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 0; i < vals.size(); ++i){
| ~~^~~~~~~~~~~~~
closing.cpp:151:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i = 0; i < vals.size(); ++i){
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
108 ms |
58608 KB |
Output is correct |
| 2 |
Correct |
119 ms |
57292 KB |
Output is correct |
| 3 |
Correct |
68 ms |
17732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12632 KB |
1st lines differ - on the 1st token, expected: '30', found: '31' |
| 4 |
Halted |
0 ms |
0 KB |
- |
