#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
const long long inf=1e18+7;
using Graph = vector<vector<pair<int, long long>>> ;
void dfs(int x,int par,Graph &edge,vector<long long>&dist)
{
for(auto [node,value]:edge[x])
{
if(node==par)continue;
dist[node]=dist[x]+value;
dfs(node,x,edge,dist);
}
}
int Sub1(int N,long long K,vector<ll>distX,vector<ll>distY)
{
vector<ll>que;
for(int i=1; i<=N; i++)
{
que.push_back(distX[i]);
que.push_back(distY[i]);
}
sort(que.begin(),que.end());
ll res=K;
int ans=0;
for(int value:que)
{
if(res<value)break;
res-=value;
ans++;
}
return ans;
}
bool checkLinear(int N,Graph edge,vector<int>°)
{
int maxv=0;
for(int i=1; i<=N; i++)
{
for(auto [x,w]:edge[i])deg[x]++;
maxv=max(maxv,deg[i]);
}
return maxv<=2;
}
void bfs(int N,int need_node,Graph edge,vector<int>&beg)
{
queue<int>q;
vector<bool>check(N+1,false);
q.push(need_node);
check[need_node]=true;
int cnt=0;
while(!q.empty())
{
int x=q.front();
q.pop();
beg[x]=++cnt;
for(auto [node,w]:edge[x])
{
if(check[node])continue;
check[node]=true;
q.push(node);
}
}
}
struct node
{
long long x;
int bonus,index;
node(int _x=0,int _index=0,int _bonus=0)
{
x=_x,index=_index,bonus=_bonus;
}
};
bool cmp(node &a,node &b)
{
return (a.x*(3-a.bonus)<b.x*(3-b.bonus));
}
int Onlyone(int N,long long K,Graph edge,vector<long long>distX,vector<long long>distY)
{
int ans=0;
vector<long long>q;
for(int i=1; i<=N; i++)
{
q.push_back(distX[i]);
q.push_back(distY[i]);
}
sort(q.begin(),q.end());
for(long long value:q)
{
if(K>=value)
{
K-=value;
ans++;
}
}
return ans;
}
int Sub2(int N,int X,int Y,long long K,Graph edge,vector<int>deg,vector<long long >distX,vector<long long>distY)
{
int need_node;
for(int i=1; i<=N; i++)if(deg[i]==1)need_node=i;
vector<int>beg(N+1);
bfs(N,need_node,edge,beg);
if(beg[X]>beg[Y])swap(X,Y);
int pre=Onlyone(N,K,edge,distX,distY);
vector<node>block;
vector<int>cnt(N+1,0);
int ans=0;
vector<int>index(N+1);
for(int i=1; i<=N; i++)index[beg[i]]=i;
for(int i=1; i<=N; i++)
{
if((beg[i]>=beg[X]&&beg[i]<=beg[Y]))continue;
long long value_x=min(distX[i],distY[i]);
long long value_y=max(distX[i],distY[i]);
if(value_y-value_x>=value_x)
{
block.push_back({value_x,i,1});
block.push_back({value_y-value_x,i,1});
}
else block.push_back({value_y,i,2});
}
for(int i=beg[X]; i<=beg[Y]; i++)
{
int node=index[i];
long long value_x=min(distX[node],distY[node]);
long long value_y=max(distX[node],distY[node]);
K-=value_x;
ans++;
cnt[node]=1;
block.push_back({value_y-value_x,node,1});
}
sort(block.begin(),block.end(),cmp);
if(K>=0)
{
for(node &need:block)
{
if(K>=need.x)
{
K-=need.x;
cnt[need.index]+=need.bonus;
ans+=need.bonus;
need.bonus=0;
}
}
set<pair<long long,int> >s;
for(node need:block)if(need.bonus==2)s.insert(make_pair(min(distX[need.index],distY[need.index]),need.index));
for(auto [value,index]:s)
{
if(K>=value)
{
K-=value;
ans+=1;
cnt[index]+=1;
}
}
multiset<long long>pX,pY;
for(int i=1; i<=N; i++)
{
if(cnt[i]==0)pY.insert(max(distX[i],distY[i]));
if(beg[i]>=beg[X]&&beg[i]<=beg[Y])continue;
if(cnt[i]==1)pX.insert(min(distX[i],distY[i]));
}
while(pX.size()>0&&pY.size()>0)
{
auto value_x=prev(pX.end());
auto value_y=pY.begin();
long long value=*value_y-*value_x;
if(K>=value)
{
K-=value;
ans++;
pX.erase(value_x);
pY.erase(value_y);
}
else break;
}
pre=max(ans,pre);
}
return pre;
}
int Sub3(int N,int X,int Y,long long K,Graph edge,vector<long long>distX,vector<long long>distY)
{
int pre=Onlyone(N,K,edge,distX,distY);
vector<bool>check(N+1,false);
for(int i=1;i<=N;i++)if(distX[i]+distY[i]==distX[Y])check[i]=true;
vector<int>beg(N+1);
vector<int>index(N+1);
bfs(N,X,edge,beg);
for(int i=1;i<=N;i++)index[beg[i]]=i;
vector<vector<long long> >dp(N+7,vector<long long>(2*N+7,inf));
dp[0][0]=0;
for(int i=1;i<=N;i++)
{
for(int cnt=0;cnt<=2*(i-1);cnt++)
{
int node=index[i];
if(check[node])
{
dp[i][cnt+1]=min(dp[i][cnt+1],dp[i-1][cnt]+min(distX[node],distY[node]));
dp[i][cnt+2]=min(dp[i][cnt+2],dp[i-1][cnt]+max(distX[node],distY[node]));
}
else
{
dp[i][cnt]=min(dp[i][cnt],dp[i-1][cnt]);
dp[i][cnt+1]=min(dp[i][cnt+1],dp[i-1][cnt]+min(distX[node],distY[node]));
dp[i][cnt+2]=min(dp[i][cnt+2],dp[i-1][cnt]+max(distX[node],distY[node]));
}
}
}
int ans=0;
for(int i=0;i<=2*N;i++)if(dp[N][i]<=K)ans=i;
return ans;
}
int max_score(int N,int X,int Y,long long K,vector<int>U,vector<int>V,vector<int>W)
{
X+=1;
Y+=1;
Graph edge(N+1);
for(int i=1; i<=N-1; i++)
{
int x=U[i-1]+1;
int y=V[i-1]+1;
int value=W[i-1];
edge[x].push_back({y,value});
edge[y].push_back({x,value});
}
vector<long long>distX(N+1);
vector<long long>distY(N+1);
dfs(X,0,edge,distX);
dfs(Y,0,edge,distY);
if(distX[Y]>2*K)return Sub1(N,K,distX,distY);
vector<int>deg(N+1);
//if(checkLinear(N,edge,deg))return Sub2(N,X,Y,K,edge,deg,distX,distY);
return Sub3(N,X,Y,K,edge,distX,distY);
}
/*signed main()
{
int n,x,y,k;
vector<int>U;
vector<int>V;
vector<int>W;
cin>>n>>x>>y>>k;
for(int i=1; i<=n-1; i++)
{
int x;
cin>>x;
U.push_back(x);
}
for(int i=1; i<=n-1; i++)
{
int y;
cin>>y;
V.push_back(y);
}
for(int i=1; i<=n-1; i++)
{
int value;
cin>>value;
W.push_back(value);
}
cout<<max_score(n,x,y,k,U,V,W);
}*/
Compilation message
closing.cpp: In function 'int Sub2(int, int, int, long long int, Graph, std::vector<int>, std::vector<long long int>, std::vector<long long int>)':
closing.cpp:119:30: warning: narrowing conversion of 'value_x' from 'long long int' to 'int' [-Wnarrowing]
119 | block.push_back({value_x,i,1});
| ^~~~~~~
closing.cpp:120:37: warning: narrowing conversion of '(value_y - value_x)' from 'long long int' to 'int' [-Wnarrowing]
120 | block.push_back({value_y-value_x,i,1});
| ~~~~~~~^~~~~~~~
closing.cpp:122:31: warning: narrowing conversion of 'value_y' from 'long long int' to 'int' [-Wnarrowing]
122 | else block.push_back({value_y,i,2});
| ^~~~~~~
closing.cpp:132:33: warning: narrowing conversion of '(value_y - value_x)' from 'long long int' to 'int' [-Wnarrowing]
132 | block.push_back({value_y-value_x,node,1});
| ~~~~~~~^~~~~~~~
closing.cpp: In function 'int Sub3(int, int, int, long long int, Graph, std::vector<long long int>, std::vector<long long int>)':
closing.cpp:186:9: warning: unused variable 'pre' [-Wunused-variable]
186 | int pre=Onlyone(N,K,edge,distX,distY);
| ^~~
closing.cpp: In function 'int Sub2(int, int, int, long long int, Graph, std::vector<int>, std::vector<long long int>, std::vector<long long int>)':
closing.cpp:104:8: warning: 'need_node' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | bfs(N,need_node,edge,beg);
| ~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
36808 KB |
Output is correct |
| 2 |
Correct |
136 ms |
43368 KB |
Output is correct |
| 3 |
Correct |
73 ms |
2900 KB |
Output is correct |
| # |
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 |
0 ms |
544 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 6 |
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 |
0 ms |
544 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 6 |
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 |
0 ms |
544 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
2nd lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
