Submission #379700

#	Time	Username	Problem	Language	Result	Execution time	Memory
379700		jamielim	Chase (CEOI17_chase)	C++14	0 / 100	524 ms	169580 KiB

chase

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n,v;
ll arr[100005];
vector<int> adj[100005];
ll sum[100005];
ll dp[2][105][100005];
ll ans=0;

inline ll mx(ll x,ll y){return (x>y?x:y);}

void dfs(int x,int p){
	for(int i:adj[x]){
		if(i==p)continue;
		dfs(i,x);
	}
	for(int j=0;j<=v;j++){
		dp[0][j][x]=dp[1][j][x]=0;
		if(j!=0){
			for(int i:adj[x]){
				if(i==p)continue;
				dp[0][j][x]=mx(dp[0][j][x],dp[0][j-1][i]-arr[i]);
				dp[1][j][x]=mx(dp[1][j][x],dp[1][j-1][i]);
			}
			dp[0][j][x]+=sum[x];
			dp[1][j][x]+=sum[x]-arr[p];
		}
		for(int i:adj[x]){
			if(i==p)continue;
			dp[0][j][x]=mx(dp[0][j][x],dp[0][j][i]);
			dp[1][j][x]=mx(dp[1][j][x],dp[1][j][i]);
		}
	}
}

void dfs2(int x,int p){
	for(int j=0;j<=v;j++){
		if(j<v){
			ii idk[2][2];idk[0][0]=idk[0][1]=mp(0,-1);idk[1][0]=idk[1][1]=mp(0,-2);
			for(int i:adj[x]){
				if(i==p)continue;
				if(dp[0][j][i]+sum[x]-arr[i]>idk[0][1].fi)idk[0][1]=mp(dp[0][j][i]+sum[x]-arr[i],i);
				if(idk[0][1].fi>idk[0][0].fi)swap(idk[0][1],idk[0][0]);
				if(dp[1][v-j-1][i]>idk[1][1].fi)idk[1][1]=mp(dp[1][v-j-1][i],i);
				if(idk[1][1].fi>idk[1][0].fi)swap(idk[1][1],idk[1][0]);
			}
			if(idk[0][0].se!=idk[1][0].se)ans=mx(ans,idk[0][0].fi+idk[1][0].fi);
			else ans=mx(ans,mx(idk[0][0].fi+idk[1][1].fi,idk[0][1].fi+idk[1][0].fi));
			//printf("%lld %d %d\n",ans,j,x);
		}
		ii idk[2][2];idk[0][0]=idk[0][1]=mp(0,-1);idk[1][0]=idk[1][1]=mp(0,-2);
		for(int i:adj[x]){
			if(i==p)continue;
			if(dp[0][j][i]>idk[0][1].fi)idk[0][1]=mp(dp[0][j][i],i);
			if(idk[0][1].fi>idk[0][0].fi)swap(idk[0][1],idk[0][0]);
			if(dp[1][v-j][i]>idk[1][1].fi)idk[1][1]=mp(dp[1][v-j][i],i);
			if(idk[1][1].fi>idk[1][0].fi)swap(idk[1][1],idk[1][0]);
		}
		if(idk[0][0].se!=idk[1][0].se)ans=mx(ans,idk[0][0].fi+idk[1][0].fi);
		else ans=mx(ans,mx(idk[0][0].fi+idk[1][1].fi,idk[0][1].fi+idk[1][0].fi));
		//printf("%lld %d %d\n",ans,j,x);
	}

}

int main(){
	scanf("%d%d",&n,&v);
	for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
	int a,b;
	for(int i=1;i<n;i++){
		scanf("%d%d",&a,&b);a--;b--;
		adj[a].pb(b);adj[b].pb(a);
	}
	for(int i=0;i<n;i++)for(int j:adj[i])sum[i]+=arr[j];
	dfs(0,-1);
	dfs2(0,-1);
	printf("%lld",ans);
}

/*

12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12

*/

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  scanf("%d%d",&n,&v);
      |  ~~~~~^~~~~~~~~~~~~~
chase.cpp:84:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |  for(int i=0;i<n;i++)scanf("%lld",&arr[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf("%d%d",&a,&b);a--;b--;
      |   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30