oj.uz

답안 #136337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136337 2019-07-25T07:10:21 Z BThero Chase (CEOI17_chase) C++17
100 / 100
 2792 ms 332704 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[2][105][MAXN], dp2[2][105][MAXN];

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 s = 0; s < 2; ++s) {
        for (int k = 0; k <= lim; ++k) {
            dp[s][k][v] = -INF;
            dp2[s][k][v] = -INF;
        }
    }
    
    for (int i = 0; i <= lim; ++i) {
        dp2[0][i][v] = 0;
        
        if (i > 0) {
            dp2[1][i][v] = neigh[v];
        }
    }

    for (int to : adj[v]) {
        if (to != pr) {
            dfs(to, v);
            
            for (int k = 0; k <= lim; ++k) {
                upd(dp2[0][k][v], max(dp2[1][k][to], dp2[0][k][to]));
                upd(dp2[1][k + 1][v], max(dp2[0][k][to], dp2[1][k][to]) + neigh[v] - arr[to]);
            }
        }
    }
    
    for (int step = 0; step < 2; ++step) {
        for (int s = 0; s < 2; ++s) {
            for (int k = 0; k <= lim; ++k) {
                dp[s][k][v] = -INF;
            }
        }
        
        for (int i = 0; i <= lim; ++i) {
            dp[0][i][v] = 0;
            
            if (i > 0) {
                dp[1][i][v] = neigh[v];
            }
        }
        
        for (int to : adj[v]) {
            if (to != pr) {
                for (int a = 0; a <= lim; ++a) {
                    int b = lim - a;
                    upd(ans, dp[0][a][v] + dp2[1][b][to]);
                    upd(ans, dp[0][a][v] + dp2[0][b][to]);
                    upd(ans, dp[1][a][v] + dp2[1][b][to] - arr[to]);
                    upd(ans, dp[1][a][v] + dp2[0][b][to] - arr[to]);
                }
                
                for (int k = 0; k <= lim; ++k) {
                    upd(dp[0][k][v], max(dp[1][k][to] - arr[v], dp[0][k][to]));
                    upd(dp[1][k + 1][v], max(dp[0][k][to], dp[1][k][to] - 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 s = 0; s < 2; ++s) {
        for (int k = 0; k <= lim; ++k) {
            for (int i = 1; i <= n; ++i) {
                upd(ans, dp[s][k][i]);
                upd(ans, dp2[s][k][i]);
            }
        }
    }
    
    printf("%lld\n", ans);
}

int main() {
    int tt = 1;

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

    return 0;
}

Compilation message

chase.cpp: In function 'void solve()':
chase.cpp:111: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:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
chase.cpp:119: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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2936 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2812 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2936 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2812 KB Output is correct
7 Correct 19 ms 8260 KB Output is correct
8 Correct 5 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 20 ms 8184 KB Output is correct
11 Correct 7 ms 4472 KB Output is correct
12 Correct 5 ms 3320 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1748 ms 330368 KB Output is correct
2 Correct 1750 ms 330444 KB Output is correct
3 Correct 1296 ms 323988 KB Output is correct
4 Correct 113 ms 14968 KB Output is correct
5 Correct 2713 ms 321912 KB Output is correct
6 Correct 2727 ms 324984 KB Output is correct
7 Correct 2741 ms 325180 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 4 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2936 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2812 KB Output is correct
7 Correct 19 ms 8260 KB Output is correct
8 Correct 5 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 20 ms 8184 KB Output is correct
11 Correct 7 ms 4472 KB Output is correct
12 Correct 5 ms 3320 KB Output is correct
13 Correct 1748 ms 330368 KB Output is correct
14 Correct 1750 ms 330444 KB Output is correct
15 Correct 1296 ms 323988 KB Output is correct
16 Correct 113 ms 14968 KB Output is correct
17 Correct 2713 ms 321912 KB Output is correct
18 Correct 2727 ms 324984 KB Output is correct
19 Correct 2741 ms 325180 KB Output is correct
20 Correct 2782 ms 327280 KB Output is correct
21 Correct 103 ms 13944 KB Output is correct
22 Correct 2792 ms 327004 KB Output is correct
23 Correct 122 ms 17016 KB Output is correct
24 Correct 2775 ms 327128 KB Output is correct
25 Correct 1306 ms 325440 KB Output is correct
26 Correct 1783 ms 332552 KB Output is correct
27 Correct 1758 ms 332704 KB Output is correct