oj.uz

Submission #379729

# Submission time Handle Problem Language Result Execution time Memory
379729 2021-03-19T06:09:55 Z errorgorn Chase (CEOI17_chase) C++17
100 / 100
 579 ms 263788 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

int n,k;
ll arr[100005];
vector<int> al[100005];

ll adj[100005];
ll w1[100005][105]; //asc
ll w2[100005][105]; //dsc

ll ans=0;

void dfs(int i,int p){
	ll temp1[105];
	ll temp2[105];
	ll temp3[105];
	
	memset(temp1,0,sizeof(temp1));
	memset(temp2,0,sizeof(temp2));
	memset(temp3,0,sizeof(temp3));
	
	for (auto &it:al[i]){
		if (it==p) continue;
		
		dfs(it,i);
		
		rep(x,0,k){ //combine 2 and this is taken
			ans=max(ans,temp1[k-x-1]+w2[it][x]+adj[i]-arr[it]);
			ans=max(ans,w1[it][x]+temp2[k-x-1]+adj[i]);
		}
		rep(x,0,k){
			ans=max(ans,temp1[k-x]+w2[it][x]);
			ans=max(ans,w1[it][x]+temp3[k-x]);
		}
		
		rep(x,0,k){
			ans=max(ans,w1[it][x]+adj[i]);
			w1[i][x]=max(w1[i][x],w1[it][x]);
			if (p!=-1) w1[i][x+1]=max(w1[i][x+1],w1[it][x]+adj[i]-arr[p]);
			
			temp1[x]=max(temp1[x],w1[it][x]);
		}
		rep(x,0,k){
			ans=max(ans,w2[it][x]+adj[i]-arr[it]);
			w2[i][x]=max(w2[i][x],w2[it][x]);
			w2[i][x+1]=max(w2[i][x+1],w2[it][x]+adj[i]-arr[it]);
			
			temp2[x]=max(temp2[x],w2[it][x]-arr[it]);
			temp3[x]=max(temp3[x],w2[it][x]);
		}
	}
	
	rep(x,1,k) w2[i][x]=max(w2[i][x],adj[i]);
	
	//cout<<"ans: "<<i<<" "<<ans<<endl;
	
	//cout<<i<<": "<<endl;
	//rep(x,0,k) cout<<w1[i][x]<<" "; cout<<endl;
	//rep(x,0,k) cout<<w2[i][x]<<" "; cout<<endl;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x];
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
		
		adj[a]+=arr[b];
		adj[b]+=arr[a];
	}
	
	/*
	dfs(4,-1);
	cout<<ans<<endl;
	return 0;
	*/
	
	dfs(1,-1);
	
	cout<<ans<<endl;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 7 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 4 ms 3564 KB Output is correct
10 Correct 6 ms 4332 KB Output is correct
11 Correct 5 ms 4332 KB Output is correct
12 Correct 4 ms 4332 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 579 ms 261868 KB Output is correct
2 Correct 566 ms 262052 KB Output is correct
3 Correct 313 ms 92260 KB Output is correct
4 Correct 209 ms 146028 KB Output is correct
5 Correct 436 ms 162328 KB Output is correct
6 Correct 456 ms 162156 KB Output is correct
7 Correct 426 ms 162032 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 2 ms 2668 KB Output is correct
4 Correct 2 ms 2668 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 7 ms 5356 KB Output is correct
8 Correct 5 ms 5356 KB Output is correct
9 Correct 4 ms 3564 KB Output is correct
10 Correct 6 ms 4332 KB Output is correct
11 Correct 5 ms 4332 KB Output is correct
12 Correct 4 ms 4332 KB Output is correct
13 Correct 579 ms 261868 KB Output is correct
14 Correct 566 ms 262052 KB Output is correct
15 Correct 313 ms 92260 KB Output is correct
16 Correct 209 ms 146028 KB Output is correct
17 Correct 436 ms 162328 KB Output is correct
18 Correct 456 ms 162156 KB Output is correct
19 Correct 426 ms 162032 KB Output is correct
20 Correct 435 ms 162176 KB Output is correct
21 Correct 161 ms 91796 KB Output is correct
22 Correct 465 ms 162028 KB Output is correct
23 Correct 211 ms 145772 KB Output is correct
24 Correct 443 ms 162284 KB Output is correct
25 Correct 288 ms 91876 KB Output is correct
26 Correct 544 ms 263788 KB Output is correct
27 Correct 556 ms 263740 KB Output is correct