Submission #1245340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245340		Nika533	Chase (CEOI17_chase)	C++20	30 / 100	136 ms	15868 KiB

chase

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,m,T,k,arr[N],val[N],parent[N];
vector<int> g[N];
int ans=0;
multiset<int> myset;
void dfs(int x, int p) {
	parent[x]=p;
	int VAL=0;
	if (parent[p]!=p) VAL=arr[parent[p]];
	if (x!=p) myset.insert(-val[p]+VAL);
	int k1=k;
	int sum2=0;
	myset.insert(-val[x]+arr[p]);
	for (auto it=myset.begin(); it!=myset.end(); it++) {
		k1--;
		sum2-=*it;
		if (k1==0) break;
	}
	myset.erase(myset.find(-val[x]+arr[p]));
	ans=max(ans,sum2);
//	cout<<x<<" "<<sum2<<endl;
	for (auto y:g[x]) {
		if (y==p) continue;
		dfs(y,x);
	}
	if (x!=p) myset.erase(myset.find(-val[p]+VAL));
}
void test_case() {
	cin>>n>>k;
	for (int i=1; i<=n; i++) cin>>arr[i];
	for (int i=1; i<=n-1; i++) {
		int a,b; cin>>a>>b;
		g[a].pb(b); g[b].pb(a);
	}
	for (int i=1; i<=n; i++) {
		for (auto j:g[i]) val[i]+=arr[j];
	}
	dfs(1,1);
	if (n<=1000) {
		for (int i=2; i<=n; i++) dfs(i,i);
	}
	cout<<ans<<endl;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	T=1;
	while (T--) test_case();
}

/*
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:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
chase.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main () {
      | ^~~~

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