oj.uz

Submission #1035294

# Submission time Handle Problem Language Result Execution time Memory
1035294 2024-07-26T08:54:45 Z MarwenElarbi Chase (CEOI17_chase) C++17
70 / 100
 1222 ms 99784 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
const int MOD=1e9+9;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int tab[nax];
long long sum[nax];
long long dp[nax][105];
vector<pair<int,ll>> adj[nax];
long long dfs(int x,int lvl,int p){
    if(dp[x][lvl]!=0) return dp[x][lvl];
    if(lvl<=0) return 0;
    dp[x][lvl]=0;
    for(auto u:adj[x]){ 
        if(u.fi==p) continue;
        dp[x][lvl]=max(dp[x][lvl],u.se+dfs(u.fi,lvl-1,x));
        dp[x][lvl]=max(dp[x][lvl],dfs(u.fi,lvl,x));
    }
    return dp[x][lvl];
}
ll ans=0;
int main()
{
    optimise;
    int n,k;
    cin>>n>>k;
    for (int i = 0; i < n; ++i)
    {
        cin>>tab[i];
    }
    for (int i = 0; i < n-1; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        sum[x]+=tab[y];
        sum[y]+=tab[x];
        adj[x].pb({y,0});
        adj[y].pb({x,0});
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < adj[i].size(); ++j)
        {
            adj[i][j].se=sum[adj[i][j].fi]-tab[i];
        }
    }
    if(n>1000){
        ans=max(dfs(0,k,-1),dfs(0,k-1,-1)+sum[0]);    
    }else{
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                memset(dp[j],0,sizeof dp[j]);
            }
            ans=max(ans,max(dfs(i,k,-1),dfs(i,k-1,-1)+(k>0 ? sum[i] : 0)));
        }
    }
    cout <<ans<<endl;
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int j = 0; j < adj[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2816 KB Output is correct
6 Correct 1 ms 2656 KB Output is correct
7 Correct 1222 ms 3780 KB Output is correct
8 Correct 127 ms 3672 KB Output is correct
9 Correct 97 ms 3676 KB Output is correct
10 Correct 242 ms 3676 KB Output is correct
11 Correct 270 ms 3676 KB Output is correct
12 Correct 198 ms 3676 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 768 ms 99784 KB Output is correct
2 Correct 712 ms 99664 KB Output is correct
3 Correct 68 ms 92672 KB Output is correct
4 Correct 85 ms 93044 KB Output is correct
5 Correct 302 ms 92964 KB Output is correct
6 Correct 249 ms 93104 KB Output is correct
7 Correct 324 ms 92988 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2816 KB Output is correct
6 Correct 1 ms 2656 KB Output is correct
7 Correct 1222 ms 3780 KB Output is correct
8 Correct 127 ms 3672 KB Output is correct
9 Correct 97 ms 3676 KB Output is correct
10 Correct 242 ms 3676 KB Output is correct
11 Correct 270 ms 3676 KB Output is correct
12 Correct 198 ms 3676 KB Output is correct
13 Correct 768 ms 99784 KB Output is correct
14 Correct 712 ms 99664 KB Output is correct
15 Correct 68 ms 92672 KB Output is correct
16 Correct 85 ms 93044 KB Output is correct
17 Correct 302 ms 92964 KB Output is correct
18 Correct 249 ms 93104 KB Output is correct
19 Correct 324 ms 92988 KB Output is correct
20 Incorrect 133 ms 93268 KB Output isn't correct
21 Halted 0 ms 0 KB -