#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=3000+10;
struct yal{
int u,v,w;
int getad(int fu){
return (u^v^fu);
}
}alle[maxn];
long long n,x,y,k,dp1[maxn][maxn],inf=1e18+1,dp2[maxn][maxn],dp[maxn][maxn];
vector<int>adj[maxn];
vector<pair<long long,long long>>all;
int inp[maxn];
vector<int>ezaf;
void clear(){
all.clear();
for(int i=0;i<=n;i++){
inp[i]=0;
adj[i].clear();
for(int j=0;j<=n;j++){
dp1[i][j]=dp2[i][j]=dp[i][j]=inf;
}
}
}
void dfsdp(int u,int par=-1){
if(par==-1){
ezaf.push_back(0);
}else{
ezaf.push_back(all[u].first);
}
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=par&&inp[v]==0){
dfsdp(v,u);
}
}
}
void boro(int u){
dfsdp(u);
sort(ezaf.begin(),ezaf.end());
for(int i=1;i<=(int)ezaf.size();i++){
dp[u][i]=dp[u][i-1]+ezaf[i-1];
}
for(int i=(int)ezaf.size()+1;i<=n+1;i++){
dp[u][i]=inf;
}
ezaf.clear();
}
int findpath(int u,int had,int par=-1){
int ret=0;
if(had==u){
ret=1;
inp[u]=1;
return 1;
}
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=par){
ret|=findpath(v,had,u);
}
}
if(ret){
inp[u]=1;
}
return ret;
}
void dfs(int u,int vas,long long mas=0,int par=-1){
if(vas==0){
all[u].first=mas;
}else{
all[u].second=mas;
}
for(auto x:adj[u]){
int v=alle[x].getad(u);
if(v!=par){
dfs(v,vas,mas+alle[x].w,u);
}
}
}
void calall(){
dfs(x,0);
dfs(y,1);
for(int i=0;i<n;i++){
if(all[i].second<all[i].first){
swap(all[i].first,all[i].second);
}
}
}
int calres(){
vector<long long>hey;
for(int i=0;i<n;i++){
hey.push_back(all[i].first);
}
sort(hey.begin(),hey.end());
long long ret=0,unnow=0;
for(int i=0;i<n;i++){
if(hey[i]+unnow<=k){
unnow+=hey[i];
ret++;
}else{
break;
}
}
vector<pair<int,int>>wtf;
int cnt=0;
set<pair<int,int>>st;
vector<int>last(n+1),tof(n+1);
for(int i=0;i<n;i++){
if(inp[i]){
k-=all[i].first;
cnt++;
last[i]=2;
wtf.push_back(make_pair(all[i].second-all[i].first,i));
}
}
if(k<0){
return ret;
}
sort(wtf.rbegin(),wtf.rend());
vector<pair<int,int>>allv;
for(int i=0;i<(int)wtf.size();i++){
for(int j=1;j<=n;j++){
if(dp[wtf[i].second][j]>=inf){
break;
}
// cout<<wtf[i].second<<" "<<j<<" "<<dp[wtf[i].second][j]<<endl;
allv.push_back(make_pair(dp[wtf[i].second][j],dp[wtf[i].second][j]+wtf[i].first));
}
}
for(int i=0;i<=n+1;i++){
for(int j=0;j<=n+1;j++){
dp2[i][j]=dp1[i][j]=inf;
}
}
dp1[0][0]=dp2[(int)allv.size()+1][0]=0;
for(int i=1;i<=(int)allv.size();i++){
// cout<<allv[i-1].first<<" "<<allv[i-1].second<<endl;
for(int j=0;j<=i;j++){
dp1[i][j]=dp1[i-1][j];
if(j>0){
dp1[i][j]=min(dp1[i][j],dp1[i-1][j-1]+allv[i-1].first);
}
}
}
for(int i=(int)allv.size();i>=1;i--){
for(int j=0;j<=i;j++){
dp2[i][j]=dp2[i+1][j];
if(j>0){
dp2[i][j]=min(dp2[i][j],dp2[i+1][j-1]+allv[i-1].second);
}
}
}
for(int i=0;i<=n;i++){
for(long long j=0;j<=n;j++){
for(int h=0;h<=n;h++){
if(dp1[i][j]+dp2[i+1][h]>k){
break;
}else{
ret=max(ret,j+h*2);
}
}
}
}
// cout<<dp1[5][4]<<" "<<dp2[6][1]<<endl;
return ret;
}
int max_score(int N, int X, int Y, long long K,
std::vector<int> U, std::vector<int> V, std::vector<int> W){
n=N;
x=X;
y=Y;
k=K;
for(int i=0;i<n-1;i++){
alle[i].u=U[i];
alle[i].v=V[i];
alle[i].w=W[i];
adj[alle[i].u].push_back(i);
adj[alle[i].v].push_back(i);
}
all.resize(n);
calall();
findpath(x,y);
for(int i=0;i<n;i++){
if(inp[i]){
boro(i);
}
}
long long ret=calres();
clear();
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
19512 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 |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '30', found: '18' |
| 4 |
Halted |
0 ms |
0 KB |
- |
