oj.uz

Submission #101593

# Submission time Handle Problem Language Result Execution time Memory
101593 2019-03-19T04:48:55 Z jamielim Chase (CEOI17_chase) C++14
40 / 100
 4000 ms 93464 KB 
#include <bits/stdc++.h>
using namespace std;

int n,v;
vector<int> adj[100005];
long long arr[100005];
long long pigeons[100005];
long long memo[100005][105];
long long dp(int x,int vleft,int p){
    if(memo[x][vleft]!=-1)return memo[x][vleft];
    if(vleft==0)return memo[x][0]=0;
    if(adj[x].size()==0)return memo[x][vleft]=pigeons[x]-(p==-1?0:arr[p]);
    long long ans=0;
    for(int i=0;i<(int)adj[x].size();i++){
        if(adj[x][i]==p)continue;
        ans=max(ans,max(dp(adj[x][i],vleft,x),dp(adj[x][i],vleft-1,x)+pigeons[x]-(p==-1?0:arr[p])));
    }
    return memo[x][vleft]=ans;
}

int main(){
    scanf("%d%d",&n,&v);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    int a,b;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&a,&b); a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        pigeons[i]=0;
        for(int j=0;j<(int)adj[i].size();j++){
            pigeons[i]+=arr[adj[i][j]];
        }
    }
    if(n<=1000){
        long long ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<=v;k++){
                    memo[j][k]=-1;
                }
            }
            ans=max(ans,dp(i,v,-1));
        }
        printf("%lld",ans);
        return 0;
    }
    memset(memo,-1,sizeof(memo));
    long long ans=dp(0,v,-1);
    for(int i=0;i<50000000/n/v;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<=v;k++){
                memo[j][k]=-1;
            }
        }
        ans=max(ans,dp(rand()%n,v,-1));
    }
    printf("%lld",ans);
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:24:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d",&arr[i]);
                    ~~~~~~~^
chase.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&v);
     ~~~~~^~~~~~~~~~~~~~
chase.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~
chase.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b); a--; b--;
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 1832 ms 3620 KB Output is correct
8 Correct 130 ms 3704 KB Output is correct
9 Correct 49 ms 3600 KB Output is correct
10 Correct 329 ms 3676 KB Output is correct
11 Correct 246 ms 3584 KB Output is correct
12 Correct 205 ms 3584 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4037 ms 93464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 1832 ms 3620 KB Output is correct
8 Correct 130 ms 3704 KB Output is correct
9 Correct 49 ms 3600 KB Output is correct
10 Correct 329 ms 3676 KB Output is correct
11 Correct 246 ms 3584 KB Output is correct
12 Correct 205 ms 3584 KB Output is correct
13 Execution timed out 4037 ms 93464 KB Time limit exceeded
14 Halted 0 ms 0 KB -