oj.uz

Submission #136342

# Submission time Handle Problem Language Result Execution time Memory
136342 2019-07-25T07:17:07 Z BThero Chase (CEOI17_chase) C++17
100 / 100
 751 ms 342236 KB 
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << '\n';

#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;   
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)1e5 + 5;
const ll INF = (ll)1e15;

ll dp[MAXN][2][105], dp2[MAXN][2][105];

vector<int> adj[MAXN];

ll neigh[MAXN];

int arr[MAXN];

int n, lim;

ll ans;

void upd(ll &a, ll b) {
    if (b > a) {
        a = b;
    }
}

void dfs(int v, int pr = -1) {
    for (int i = 0; i <= lim; ++i) {
        dp2[v][0][i] = 0;
        
        if (i > 0) {
            dp2[v][1][i] = neigh[v];
        }
        else {
            dp2[v][1][i] = -INF;
        }
    }

    for (int to : adj[v]) {
        if (to != pr) {
            dfs(to, v);
            
            for (int k = 0; k <= lim; ++k) {
                upd(dp2[v][0][k], max(dp2[to][1][k], dp2[to][0][k]));
                upd(dp2[v][1][k + 1], max(dp2[to][0][k], dp2[to][1][k]) + neigh[v] - arr[to]);
            }
        }
    }
    
    for (int step = 0; step < 2; ++step) {
        for (int i = 0; i <= lim; ++i) {
            dp[v][0][i] = 0;
            
            if (i > 0) {
                dp[v][1][i] = neigh[v];
            }
            else {
                dp[v][1][i] = -INF;
            }
        }
        
        for (int to : adj[v]) {
            if (to != pr) {
                for (int a = 0; a <= lim; ++a) {
                    int b = lim - a;
                    upd(ans, dp[v][0][a] + dp2[to][1][b]);
                    upd(ans, dp[v][0][a] + dp2[to][0][b]);
                    upd(ans, dp[v][1][a] + dp2[to][1][b] - arr[to]);
                    upd(ans, dp[v][1][a] + dp2[to][0][b] - arr[to]);
                }
                
                for (int k = 0; k <= lim; ++k) {
                    upd(dp[v][0][k], max(dp[to][1][k] - arr[v], dp[to][0][k]));
                    upd(dp[v][1][k + 1], max(dp[to][0][k], dp[to][1][k] - arr[v]) + neigh[v]);
                }
            }
        }
        
        reverse(all(adj[v]));
    }
}

void solve() {
    scanf("%d %d", &n, &lim);
    
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].pb(v);
        adj[v].pb(u);
        neigh[u] += arr[v];
        neigh[v] += arr[u];
    }
    
    dfs(1);
    
    for (int i = 1; i <= n; ++i) {
        for (int s = 0; s < 2; ++s) {
            upd(ans, dp[i][s][lim]);
            upd(ans, dp2[i][s][lim]);
        }
    }
    
    printf("%lld\n", ans);
}

int main() {
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message

chase.cpp: In function 'void solve()':
chase.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &lim);
     ~~~~~^~~~~~~~~~~~~~~~~~~
chase.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
chase.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 9 ms 6008 KB Output is correct
8 Correct 8 ms 6004 KB Output is correct
9 Correct 7 ms 6008 KB Output is correct
10 Correct 9 ms 6008 KB Output is correct
11 Correct 8 ms 6008 KB Output is correct
12 Correct 7 ms 6008 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 342132 KB Output is correct
2 Correct 662 ms 341960 KB Output is correct
3 Correct 535 ms 336244 KB Output is correct
4 Correct 366 ms 335864 KB Output is correct
5 Correct 746 ms 335896 KB Output is correct
6 Correct 751 ms 335920 KB Output is correct
7 Correct 737 ms 335892 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 9 ms 6008 KB Output is correct
8 Correct 8 ms 6004 KB Output is correct
9 Correct 7 ms 6008 KB Output is correct
10 Correct 9 ms 6008 KB Output is correct
11 Correct 8 ms 6008 KB Output is correct
12 Correct 7 ms 6008 KB Output is correct
13 Correct 662 ms 342132 KB Output is correct
14 Correct 662 ms 341960 KB Output is correct
15 Correct 535 ms 336244 KB Output is correct
16 Correct 366 ms 335864 KB Output is correct
17 Correct 746 ms 335896 KB Output is correct
18 Correct 751 ms 335920 KB Output is correct
19 Correct 737 ms 335892 KB Output is correct
20 Correct 739 ms 336000 KB Output is correct
21 Correct 366 ms 335968 KB Output is correct
22 Correct 741 ms 336044 KB Output is correct
23 Correct 388 ms 335968 KB Output is correct
24 Correct 740 ms 335992 KB Output is correct
25 Correct 553 ms 336156 KB Output is correct
26 Correct 647 ms 342236 KB Output is correct
27 Correct 642 ms 342132 KB Output is correct