#include "closing.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pb push_back
#define ppb pop_back
using namespace std;
const int N=6005;
int n,dis[2][N],k;
vector<pair<int,int>> adj[N];
vector<int> st,path;
bool onpath[N];
void dfs(int x,int p,int h){
for (auto u:adj[x]){
if (u.F==p) continue;
dis[h][u.F]=dis[h][x]+u.S;
dfs(u.F,x,h);
}return;
}
void getpath(int x,int p,int y){
st.pb(x);
if (x==y) path=st;
for (auto u:adj[x]){
if (u.F==p) continue;
getpath(u.F,x,y);
}st.ppb();
return;
}
int32_t max_score(int32_t nn, int32_t X, int32_t Y, long long K,
std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W)
{
n=nn;
k=K;
st.clear();path.clear();
for (int i=0;i<n;i++) adj[i].clear(),onpath[i]=0;
for (int i=0;i<U.size();i++){
adj[U[i]].pb({V[i],W[i]});
adj[V[i]].pb({U[i],W[i]});
}dis[0][X]=0;
dfs(X,0,0);
dis[1][Y]=0;
dfs(Y,0,1);
getpath(X,0,Y);
for (auto u:path) onpath[u]=1;
priority_queue<vector<int>> pq;
for (auto u:adj[X]){
if (!onpath[u.F]) pq.push({-dis[0][u.F],u.F,0});
}
for (auto u:adj[Y]){
if (!onpath[u.F]) pq.push({-dis[1][u.F],u.F,1});
}
vector<int> v;v.pb(0);
while (!pq.empty()){
int x=pq.top()[1];bool h=pq.top()[2];
pq.pop();
v.pb(v.back()+dis[h][x]);
for (auto u:adj[x]){
if (dis[h][u.F]<dis[h][x]) continue;
pq.push({-dis[h][u.F],u.F,h});
}
}
vector<int> p,s,mx;p.resize(path.size());s.resize(path.size());mx.resize(path.size());
s[s.size()-1]=dis[1][path.back()];
for (int i=s.size()-2;i>=0;i--) s[i]=s[i+1]+dis[1][path[i]];
p[0]=dis[0][path[0]];
for (int i=1;i<p.size();i++) p[i]=p[i-1]+dis[0][path[i]];
mx[0]=max(dis[0][path[0]],dis[1][path[0]]);
for (int i=1;i<mx.size();i++) mx[i]=mx[i-1]+max(dis[0][path[i]],dis[1][path[i]]);
int ans=0;
for (int i=0;i<path.size();i++){
for (int j=path.size()-1;j>=0;j--){
int x=0;
if (i<j) x=p[i]+s[j];
else{
x=mx[i];
if (j) x-=mx[j-1],x+=p[j-1];
if (i+1<path.size()) x+=s[i+1];
}
int l=0,r=v.size()-1,mid,ansx=0;
while (l<=r){
mid=(l+r)/2;
if (v[mid]+x<=k){
ansx=mid+i+1+path.size()-j;
l=mid+1;
}else r=mid-1;
}ans=max(ans,ansx);
}
}
k-=mx.back();
if (k<=0) return ans;
for (int i=0;i<v.size();i++){
int x=k-v[i];
if (x<0) break;
ans=max(ans,(int)2*(int)path.size()+i+min((k-v[i])/dis[0][Y],i));
}
return ans;
}
Compilation message
closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:37:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i=0;i<U.size();i++){
| ~^~~~~~~~~
closing.cpp:67:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i=1;i<p.size();i++) p[i]=p[i-1]+dis[0][path[i]];
| ~^~~~~~~~~
closing.cpp:69:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int i=1;i<mx.size();i++) mx[i]=mx[i-1]+max(dis[0][path[i]],dis[1][path[i]]);
| ~^~~~~~~~~~
closing.cpp:71:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i=0;i<path.size();i++){
| ~^~~~~~~~~~~~
closing.cpp:78:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (i+1<path.size()) x+=s[i+1];
| ~~~^~~~~~~~~~~~
closing.cpp:92:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | for (int i=0;i<v.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
10368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
