oj.uz

Submission #63158

# Submission time Handle Problem Language Result Execution time Memory
63158 2018-08-01T01:29:50 Z khsoo01 Chase (CEOI17_chase) C++11
20 / 100
 783 ms 342248 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] < V) {
		T[1] = T[0];
		T[0] = V;
	}
	else if(T[0].Y != V.Y && 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:51: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:53: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:56: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 6 ms 2680 KB Output is correct
2 Correct 5 ms 2920 KB Output is correct
3 Correct 5 ms 2920 KB Output is correct
4 Correct 5 ms 2920 KB Output is correct
5 Correct 5 ms 2920 KB Output is correct
6 Correct 6 ms 2976 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 5 ms 2920 KB Output is correct
3 Correct 5 ms 2920 KB Output is correct
4 Correct 5 ms 2920 KB Output is correct
5 Correct 5 ms 2920 KB Output is correct
6 Correct 6 ms 2976 KB Output is correct
7 Incorrect 12 ms 6344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 5 ms 2920 KB Output is correct
3 Correct 5 ms 2920 KB Output is correct
4 Correct 5 ms 2920 KB Output is correct
5 Correct 5 ms 2920 KB Output is correct
6 Correct 6 ms 2976 KB Output is correct
7 Incorrect 12 ms 6344 KB Output isn't correct
8 Halted 0 ms 0 KB -