oj.uz

Submission #683838

# Submission time Handle Problem Language Result Execution time Memory
683838 2023-01-19T12:44:36 Z Theo830 Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 262444 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(int i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
ll p[100005];
ll dp[300005][105];
vector<vector<ii> >adj;
ll solve(ll idx,ll v,ll par,ll d){
    if(dp[d][v] != -1){
        return dp[d][v];
    }
    ll ans = 0;
    ll sum = 0;
    for(auto x:adj[idx]){
        if(x.F != par){
            sum += p[x.F];
            ans = max(ans,solve(x.F,v,idx,x.S));
        }
    }
    if(v){
        for(auto x:adj[idx]){
            if(x.F != par){
                ans = max(ans,sum  + solve(x.F,v-1,idx,x.S));
            }
        }
    }
    return dp[d][v] = ans;
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,v;
    cin>>n>>v;
    f(i,0,n){
        cin>>p[i+1];
    }
    adj.assign(n+5,vector<ii>());
    ll cur = n+5;
    f(i,0,n-1){
        ll a,b;
        cin>>a>>b;
        adj[a].pb(ii(b,cur));
        cur++;
        adj[b].pb(ii(a,cur));
        cur++;
    }
    ll ans = 0;
    memset(dp,-1,sizeof dp);
    f(i,1,n+1){
        ans = max(ans,solve(i,v,0,i));
    }
    cout<<ans<<"\n";
}
/*
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
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246824 KB Output is correct
2 Correct 93 ms 246756 KB Output is correct
3 Correct 93 ms 246784 KB Output is correct
4 Correct 95 ms 246868 KB Output is correct
5 Correct 96 ms 246848 KB Output is correct
6 Correct 93 ms 246924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246824 KB Output is correct
2 Correct 93 ms 246756 KB Output is correct
3 Correct 93 ms 246784 KB Output is correct
4 Correct 95 ms 246868 KB Output is correct
5 Correct 96 ms 246848 KB Output is correct
6 Correct 93 ms 246924 KB Output is correct
7 Correct 96 ms 247000 KB Output is correct
8 Correct 104 ms 247040 KB Output is correct
9 Correct 102 ms 246860 KB Output is correct
10 Correct 90 ms 246992 KB Output is correct
11 Correct 90 ms 246964 KB Output is correct
12 Correct 90 ms 246912 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 262444 KB Output is correct
2 Correct 609 ms 262420 KB Output is correct
3 Execution timed out 4058 ms 256880 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 246824 KB Output is correct
2 Correct 93 ms 246756 KB Output is correct
3 Correct 93 ms 246784 KB Output is correct
4 Correct 95 ms 246868 KB Output is correct
5 Correct 96 ms 246848 KB Output is correct
6 Correct 93 ms 246924 KB Output is correct
7 Correct 96 ms 247000 KB Output is correct
8 Correct 104 ms 247040 KB Output is correct
9 Correct 102 ms 246860 KB Output is correct
10 Correct 90 ms 246992 KB Output is correct
11 Correct 90 ms 246964 KB Output is correct
12 Correct 90 ms 246912 KB Output is correct
13 Correct 622 ms 262444 KB Output is correct
14 Correct 609 ms 262420 KB Output is correct
15 Execution timed out 4058 ms 256880 KB Time limit exceeded
16 Halted 0 ms 0 KB -