oj.uz

Submission #227750

# Submission time Handle Problem Language Result Execution time Memory
227750 2020-04-28T16:31:50 Z mohamedsobhi777 Dostavljač (COCI18_dostavljac) C++14
14 / 140
 50 ms 20992 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*5][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 -1e9 ;
    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(int j = i+1 ; j < t ;j++){
        if(euler[j] == euler[i]){
            ret = max(ret , solve(j , r )) ; 
        }
    }
    /*
    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 ) ) ; 
    return ret ; 
}

int main(){
    memset(dp , -1 , sizeof dp) ;
    ios_base::sync_with_stdio(0) ; 
    cin.tie(0) ; 
    //freopen("in.in" , "r" , stdin) ; 
    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 10368 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 14.0

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

Subtask #6
0 / 14.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 10496 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 21 ms 20992 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 21 ms 20992 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 20 ms 20992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -