Submission #63160

#	Time	Username	Problem	Language	Result	Execution time	Memory
63160		khsoo01	Chase (CEOI17_chase)	C++11	100 / 100	863 ms	367184 KiB

chase

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll N = 100005, L = 105;

ll n, c, cc, mis[N], a[N], v[N], ans;
pll dt[N][L][2];

vector<ll> adj[N];

void upd (pll T[], pll V) {
	if(T[0].Y == V.Y) {
		if(T[0] < V) T[0] = V;
	}
	else {
		if(T[0] < V) {
			T[1] = T[0];
			T[0] = V;
		}
		else if(T[1] < V) T[1] = V;
	}
}

void calc (ll T, ll C) {
	for(ll i=0;i<=c;i++) {
		ll I = (dt[T][i][0].Y == C);
		ll V = dt[T][i][I].X;
		upd(dt[C][i], pll(V, T));
		if(i < c) upd(dt[C][i+1], pll(V + v[T] - a[C], T));
	}
}

void solve (ll C, ll P) {
	if(!mis[C]) {
		for(auto &T : adj[C]) {
			if(T == P) continue;
			solve(T, C);
			calc(T, C);
		}
		mis[C] = P;
	}
	else if(mis[C] != -1 && mis[C] != P) {
		solve(mis[C], C);
		calc(mis[C], C);
		mis[C] = -1;
	}
}

int main()
{
	scanf("%lld%lld",&n,&c);
	if(!c) {puts("0"); return 0;}
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(ll i=1;i<n;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B);
		adj[A].push_back(B);
		adj[B].push_back(A);
	}
	for(ll i=1;i<=n;i++) {
		for(auto &T : adj[i]) v[i] += a[T];
	}
	for(ll i=1;i<=n;i++) {
		solve(i, -1);
		ans = max({ans, dt[i][c-1][0].X + v[i], dt[i][c][0].X});
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~
chase.cpp:56:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
                       ~~~~~^~~~~~~~~~~~~~
chase.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
   ~~~~~^~~~~~~~~~~~~~~~~~

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