oj.uz

Submission #54909

# Submission time Handle Problem Language Result Execution time Memory
54909 2018-07-05T10:51:17 Z istlemin Chase (CEOI17_chase) C++14
50 / 100
 2953 ms 104652 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n, bread;
vi p;
vector<vi> e;

vector<vi> mem;

ll dfs(ll v, ll l, ll b){
	if(b==0) return 0;
    if(mem[v][b]!=-1) return mem[v][b];
    ll best = 0;
    ll childSum = 0;
    rep(i,0,e[v].size())
		if(e[v][i]!=l)
			childSum += p[e[v][i]];

    rep(i,0,e[v].size()){
		if(e[v][i]==l) continue;
        best = max(best,childSum + dfs(e[v][i],v,b-1));
        best = max(best,dfs(e[v][i],v,b));
    }

    return mem[v][b] = best;
}

ll getBest(ll start){
    mem.assign(n,vi(bread+1,-1));
    return dfs(start,-1, bread);
}

int main(){
	cin.sync_with_stdio(false);
    cin>>n>>bread;
    p.resize(n);
    e.resize(n);
    rep(i,0,n) cin>>p[i];
	rep(i,0,n-1) {
		ll a,b;
		cin>>a>>b;
		--a; --b;
        e[a].push_back(b);
        e[b].push_back(a);
	}
    if(n>100){
		cout<<getBest(0)<<endl;
    } else {
		//cout<<getBest(5)<<endl;
		//return 0;
        ll best = 0;
        rep(i,0,n)
			best = max(best,getBest(i));
		cout<<best<<endl;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 3 ms 576 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Incorrect 9 ms 1580 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2953 ms 96724 KB Output is correct
2 Correct 2566 ms 98776 KB Output is correct
3 Correct 134 ms 98776 KB Output is correct
4 Correct 92 ms 98776 KB Output is correct
5 Correct 945 ms 100460 KB Output is correct
6 Correct 833 ms 102560 KB Output is correct
7 Correct 979 ms 104652 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 3 ms 576 KB Output is correct
7 Incorrect 9 ms 1580 KB Output isn't correct
8 Halted 0 ms 0 KB -