Submission #227746

#	Time	Username	Problem	Language	Result	Execution time	Memory
227746		mohamedsobhi777	Dostavljač (COCI18_dostavljac)	C++14	14 / 140	18 ms	16896 KiB

dostavljac

#include<bits/stdc++.h>

using namespace std ; 

const int N = 500 + 7 ;

int n , m; 
int a[N] ; 
vector<int> adj[N] ; 

int t = 1 ; 
int euler[N] , fr[N] ; 
vector<int> mov[N] ; 

int dp[N*4][500 + 7][2] ;

int dfs(int x , int p){
    fr[x] = t ; 
    euler[t++] = x ; 
    for(auto u : adj[x]){
        if(u==p)continue ; 
        mov[x].push_back(t) ; 
        dfs(u , x) ; 
        euler[t++] = x ; 
    }
    if(adj[x].size() == 1 && x !=1)
        euler[t++] = x ; 
}   

int solve(int i , int r , bool keep = 1){
    if(r < 0)return -1e7 ;
    if( i== t || !r){
        return 0 ; 
    }
    int &ret = dp[i][r][keep] ;
    if(ret!=-1)return ret ; 
    if(keep && r && fr[euler[i]] == i){
        ret = max(ret , a[euler[i]] +  solve(i , r -1 , 0)) ; 
    }
    for(auto u : mov[ euler[i] ]){
        if( u <= i)continue ; 
        ret = max(ret , solve(u , r - 1 +  (euler[i] == euler[u]))  ) ; 
    }
    ret = max(ret , solve(i+1 , r-1 + (euler[i] == euler[i+1]) ) ) ; 
    return ret ; 
}

int main(){
    memset(dp , -1 , sizeof dp) ;
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    cin>>n>>m ; 
    for(int i = 1 ;i <=n ;i++){
        cin>>a[i] ;
    }
    for(int i = 0 ;i < n-1 ;i++){
        int a , b ; 
        cin>>a>> b; 
        adj[a].push_back(b) ; 
        adj[b].push_back(a) ; 
    }
    dfs(1 , 1) ; 
    cout<<solve(1 , m); 
    return 0 ; 
}   

Compilation message (stderr)

dostavljac.cpp: In function 'int dfs(int, int)':
dostavljac.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }   
 ^

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14