oj.uz

Submission #379773

# Submission time Handle Problem Language Result Execution time Memory
379773 2021-03-19T09:22:33 Z jamielim Chase (CEOI17_chase) C++14
20 / 100
 1290 ms 172024 KB 
#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){
			dp[1][j][x]=arr[p];
			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]+sum[x]);
			}
			dp[0][j][x]+=sum[x];
			dp[1][j][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 i:adj[x]){
		if(i==p)continue;
		dfs2(i,x);
	}
	for(int j=0;j<v;j++){
		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]-arr[i]>idk[0][1].fi)idk[0][1]=mp(dp[0][j][i]-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+sum[x]);
		else ans=mx(ans,mx(idk[0][0].fi+idk[1][1].fi,idk[0][1].fi+idk[1][0].fi)+sum[x]);
		//printf("%lld %d %d\n",ans,j,x);
	}
	for(int j=0;j<=v;j++){
		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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 6 ms 2796 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 6 ms 2796 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Incorrect 13 ms 5484 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1290 ms 172024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 6 ms 2796 KB Output is correct
5 Correct 3 ms 2668 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Incorrect 13 ms 5484 KB Output isn't correct
8 Halted 0 ms 0 KB -