#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=200005;
const int maxs=3005;
#define pii pair<int,int>
#define piii pair<long long,pii>
#define fi first
#define se second
const long long inf=2e18;
long long dist[maxn][2];
long long dp2[maxs][2*maxs],dp1[maxs][maxs],nw2[2*maxs],nw1[maxs];
int sz[maxn];
vector<pii> edge[maxn];
bool check[maxn];
bool cc[maxn][2];
int max_score(int n, int X, int Y, long long K,
vector<int> U, vector<int> V, vector<int> W)
{
for(int i=0;i<n;i++){
edge[i].clear();check[i]=cc[i][0]=cc[i][1]=false;
dist[i][0]=dist[i][1]=0;sz[i]=1;
}
for(int i=0;i<n-1;i++){
edge[U[i]].push_back({V[i],W[i]});
edge[V[i]].push_back({U[i],W[i]});
}
vector<int> path;
function<void(int,int)> pre_dfs = [&](int u,int p){
if(u==Y){
path.push_back(u);
check[u]=true;
return;
}
for(auto &[v,w]:edge[u]){
if(v==p) continue;
pre_dfs(v,u);check[u]|=check[v];
}
if(check[u]) path.push_back(u);
};
pre_dfs(X,-1);
reverse(path.begin(),path.end());
function<void(int,int,int)> dfs_dist = [&](int u,int p,int t){
for(auto &[v,w]:edge[u]){
if(v==p) continue;
dist[v][t]=dist[u][t]+w;
dfs_dist(v,u,t);
}
};
dfs_dist(X,-1,0);dfs_dist(Y,-1,1);
long long res=0,sum=0;
priority_queue<piii,vector<piii>,greater<piii>> pq;
pq.push({0,{X,0}});pq.push({0,{Y,1}});
while(!pq.empty()){
long long d=pq.top().fi;
int u=pq.top().se.fi,t=pq.top().se.se;pq.pop();
if(sum+d>K) break;
sum+=d;res++;cc[u][t]=true;
for(auto &[v,w]:edge[u]){
if(!cc[v][t]) pq.push({dist[v][t],{v,t}});
}
}
if(n<=3000){
priority_queue<long long,vector<long long>,greater<long long>> pq2;
function<void(int,int)> dfs = [&](int u,int p){
pq2.push(min(dist[u][0],dist[u][1]));
for(auto &[v,w]:edge[u]){
if(v==p || check[v]) continue;
dfs(v,u);sz[u]+=sz[v];
}
};
int pos=path[0];
for(int u:path){
dfs(u,-1);
for(int i=0;i<=2*n;i++) dp1[u][i]=dp2[u][i]=inf;
int d=abs(dist[u][0]-dist[u][1]);
for(int i=1;i<=sz[u];i++) dp1[u][i]=(i==1?0:dp1[u][i-1])+pq2.top(),pq2.pop();
for(int i=sz[u];i>=1;i--){
for(int j=1;j<=i;j++) dp2[u][i+j]=min(dp2[u][i+j],dp1[u][i]+d*j);
}
if(dist[u][0]<=dist[u][1]) pos=u;
/*
cout << u << '\n';
for(int i=1;i<=sz[u];i++) cout << dp1[u][i] << ' ';
cout << '\n';
for(int i=1;i<=2*sz[u];i++) cout << (dp2[u][i]==inf?-1:dp2[u][i]) << ' ';
cout << '\n';
*/
}
function<void(int,int)> unions2 = [&](int u,int v){
for(int i=1;i<=2*(sz[u]+sz[v]);i++) nw2[i]=inf;
for(int i=1;i<=sz[u]+sz[v];i++) nw1[i]=inf;
for(int i=2*sz[u];i>=1;i--){
for(int j=1;j<=2*sz[v];j++){
nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp2[v][j]);
if(j<=sz[v]){
nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp1[v][j]);
if(i<=sz[u]) nw1[i+j]=min(nw1[i+j],dp1[u][i]+dp1[v][j]);
}
}
}
sz[u]+=sz[v];
for(int i=1;i<=2*sz[u];i++) dp2[u][i]=nw2[i];
for(int i=1;i<=sz[u];i++) dp1[u][i]=nw1[i];
};
for(int i=1;i<(int)path.size();i++){
unions2(path[i],path[i-1]);
if(path[i]==pos) break;
}
for(int t=(int)path.size()-2;t>=0;t--){
if(path[t]==pos){
int u=path[t],v=path[t+1];
for(int i=1;i<=2*(sz[u]+sz[v]);i++) nw2[i]=inf;
for(int j=1;j<=sz[u];j++) dp2[u][j]=min(dp2[u][j],dp1[u][j]);
for(int j=1;j<=sz[v];j++) dp2[v][j]=min(dp2[v][j],dp1[v][j]);
/*
for(int i=1;i<=2*sz[u];i++) cout << dp2[u][i] << ' ';
cout << '\n';
for(int i=1;i<=2*sz[v];i++) cout << dp2[v][i] << ' ';
cout << '\n';
*/
for(int i=2*sz[u];i>=1;i--){
for(int j=1;j<=2*sz[v];j++) nw2[i+j]=min(nw2[i+j],dp2[u][i]+dp2[v][j]);
}
sz[u]+=sz[v];
for(long long j=1;j<=2*sz[u];j++){
if(nw2[j]<=K) res=max(res,j);
}
break;
}
unions2(path[t],path[t+1]);
}
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
30504 KB |
Output is correct |
| 2 |
Correct |
123 ms |
40012 KB |
Output is correct |
| 3 |
Correct |
823 ms |
47048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 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 |
3 ms |
4948 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 |
3 ms |
4948 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 |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 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 |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 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 |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 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 |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 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 |
2 ms |
4948 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
4948 KB |
1st lines differ - on the 1st token, expected: '3', found: '4' |
| 3 |
Halted |
0 ms |
0 KB |
- |
