oj.uz

Submission #227746

# Submission time Handle Problem Language Result Execution time Memory
227746 2020-04-28T16:22:10 Z mohamedsobhi777 Dostavljač (COCI18_dostavljac) C++14
14 / 140
 18 ms 16896 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8448 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8448 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8448 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8448 KB Output isn't correct

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 16896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 16896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 16896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -