oj.uz

Submission #63160

# Submission time Handle Problem Language Result Execution time Memory
63160 2018-08-01T01:30:31 Z khsoo01 Chase (CEOI17_chase) C++11
100 / 100
 863 ms 367184 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2844 KB Output is correct
3 Correct 4 ms 2844 KB Output is correct
4 Correct 5 ms 2852 KB Output is correct
5 Correct 6 ms 2852 KB Output is correct
6 Correct 5 ms 2852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2844 KB Output is correct
3 Correct 4 ms 2844 KB Output is correct
4 Correct 5 ms 2852 KB Output is correct
5 Correct 6 ms 2852 KB Output is correct
6 Correct 5 ms 2852 KB Output is correct
7 Correct 12 ms 6128 KB Output is correct
8 Correct 11 ms 6256 KB Output is correct
9 Correct 9 ms 6352 KB Output is correct
10 Correct 42 ms 6464 KB Output is correct
11 Correct 13 ms 6464 KB Output is correct
12 Correct 11 ms 6464 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 340424 KB Output is correct
2 Correct 786 ms 342640 KB Output is correct
3 Correct 621 ms 342640 KB Output is correct
4 Correct 496 ms 344232 KB Output is correct
5 Correct 831 ms 346436 KB Output is correct
6 Correct 789 ms 348752 KB Output is correct
7 Correct 863 ms 350716 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 4 ms 2844 KB Output is correct
3 Correct 4 ms 2844 KB Output is correct
4 Correct 5 ms 2852 KB Output is correct
5 Correct 6 ms 2852 KB Output is correct
6 Correct 5 ms 2852 KB Output is correct
7 Correct 12 ms 6128 KB Output is correct
8 Correct 11 ms 6256 KB Output is correct
9 Correct 9 ms 6352 KB Output is correct
10 Correct 42 ms 6464 KB Output is correct
11 Correct 13 ms 6464 KB Output is correct
12 Correct 11 ms 6464 KB Output is correct
13 Correct 727 ms 340424 KB Output is correct
14 Correct 786 ms 342640 KB Output is correct
15 Correct 621 ms 342640 KB Output is correct
16 Correct 496 ms 344232 KB Output is correct
17 Correct 831 ms 346436 KB Output is correct
18 Correct 789 ms 348752 KB Output is correct
19 Correct 863 ms 350716 KB Output is correct
20 Correct 752 ms 352820 KB Output is correct
21 Correct 6 ms 352820 KB Output is correct
22 Correct 849 ms 354964 KB Output is correct
23 Correct 543 ms 356940 KB Output is correct
24 Correct 772 ms 358868 KB Output is correct
25 Correct 551 ms 360840 KB Output is correct
26 Correct 652 ms 365056 KB Output is correct
27 Correct 730 ms 367184 KB Output is correct