#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 = 3005;
const ll INF = 1e18;
int sz[N];
vector<pair<int, ll>> g[N];
ll val1[N], val2[N], dp[N][N];
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;
}
void p(int v, int pp){
sz[v] = 1;
for(auto U: g[v]){
int u = U.ff;
if(u != pp && val2[u] != -1){
p(u, v);
sz[v] += sz[u];
}
}
}
void calc(int v, int p){
dp[v][0] = 0;
dp[v][1] = val1[v];
dp[v][2] = (val2[v] == -1 ? INF : val2[v]) + val1[v];
for(int j = 3; j <= sz[v]*2; ++j) dp[v][j] = INF;
sz[v] = 2;
for(auto U: g[v]){
int u = U.ff;
if(u != p && val2[u] != -1){
calc(u, v);
sz[v] += sz[u];
for(int j = sz[v]; j >= 1; --j){
for(int l = 1; l <= min(j, sz[u]); ++l){
dp[v][j] = min(dp[v][j], dp[v][j - l] + dp[u][l]);
}
}
}
}
}
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;
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]);
}else{
val1[i] = min(D1[i], D2[i]);
val2[i] = max(D1[i], D2[i]) - val1[i];
}
}
if(K<0) return anss;
for(int v: euler){
p(v, v);
calc(v, v);
}
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 max(ans + int(euler.size()), anss);
// }
// }
// return anss;
}
Compilation message
closing.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
2 | #pragma optimize ("O3")
|
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < A.size(); ++i){
| ~~^~~~~~~~~~
closing.cpp:116:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
116 | ll lm = ls+rs>>1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
10076 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
1st lines differ - on the 1st token, expected: '30', found: '35' |
| 4 |
Halted |
0 ms |
0 KB |
- |
