#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 3e3 + 9 , mod = 1e9 + 7;
ll a[N], b[N] , c[N] , ind[N] , d[N][2] ;
vector<pair<int,int>>v[N];
void dfs(int n , int x , int p = 0) {
for(auto to : v[n])
if(to.fi != p)
d[to.fi][x] = d[n][x] + to.se , dfs(to.fi , x , n);
}
int n;
ll get(int x , int y) {
if(x < 1 || x > n)
return 1e18 + 5;
else
return d[ind[x]][0];
}
void Clear(int n ) {
for(int i = 0; i <= n + 4; i++)
v[i].clear() , d[i][0] = d[i][1] = 0, c[i] = 0, ind[i] = 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) {
ll i , j , l , r, s = 0 , f , m , ans= 0 , mxz = 0;
x++ , y++;
::n = n;
for(i = 0; i < n - 1; i++) {
l = V[i] + 1, r = U[i] + 1;
v[l].pb({r , W[i]});
v[r].pb({l , W[i]});
}
for(i = 1; i <= n; i++)
if(v[i].size() == 1)
f = i;
l = 0;
for(i = 1; i <= n; i++){
c[f] = i;
ind[i] = f;
for(auto to : v[f])
if(to.fi != l) {
l = f , f = to.fi ;
break;
}
}
if(c[x] > c[y])
swap(x , y);
dfs(x , 0);
dfs(y , 1);
f = 0;
for(i = c[x]; i <= n; i++) {
l = ind[i];
f += d[l][0];
s = f;
ll l1 = c[x] , l2 = max(i , c[y]);
ll sum = i - c[x] + 1;
if(i > c[y])
sum += (i - c[y]);
while(true) {
if(get(l1 - 1 , 0) < get(l2 + 1 , 1) && get(l1 - 1, 0) + s <= k) {
s += get(l1 - 1, 0) ,sum++ , l1--;
}else if(get(l2 + 1, 1) + s <= k){
s += get(l2 + 1, 1), sum++ , l2++;
}else {
break;
}
}
if(s <= k)
ans = max(ans , sum);
else
break;
for(j = c[y]; j >= 1; j--) {
l = ind[j];
if(j < c[x]) {
if(j >= l1)
sum -- , s -= d[l][0];
s += d[l][1] , sum += 2;
}else {
if(i >= j)
s -= d[l][0] , s += max(d[l][1] , d[l][0]);
else
s += d[l][1];
sum++;
}
while(s > k) {
if(l2 <= max(i , c[y]) && l1 >= min(j , c[x]))
break;
if((l2 > max(i, c[y]) && l1 < min(j , c[x]) && get(l2 , 1) > get(l1 , 0)) || (l1 >= min(j , c[x]))){
s -= get(l2 , 1) , l2-- , sum--;
}else {
s -= get(l1 , 0) ,l1++ , sum--;
}
}
if(s > k)
break;
ans = max(ans , sum);
}
}
Clear(n);
return ans;
}
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:44:37: warning: unused variable 'm' [-Wunused-variable]
44 | ll i , j , l , r, s = 0 , f , m , ans= 0 , mxz = 0;
| ^
closing.cpp:44:50: warning: unused variable 'mxz' [-Wunused-variable]
44 | ll i , j , l , r, s = 0 , f , m , ans= 0 , mxz = 0;
| ^~~
closing.cpp:44:33: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
44 | ll i , j , l , r, s = 0 , f , m , ans= 0 , mxz = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
39 ms |
10040 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
512 KB |
1st lines differ - on the 1st token, expected: '74', found: '71' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
512 KB |
1st lines differ - on the 1st token, expected: '74', found: '71' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Incorrect |
0 ms |
512 KB |
1st lines differ - on the 1st token, expected: '74', found: '71' |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '6', found: '5' |
| 2 |
Halted |
0 ms |
0 KB |
- |
