oj.uz

Submission #122307

# Submission time Handle Problem Language Result Execution time Memory
122307 2019-06-28T04:33:56 Z BThero Chase (CEOI17_chase) C++17
70 / 100
 1258 ms 170200 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 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)1e18;

vector<int> adj[MAXN];

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

ll neigh[MAXN];

int arr[MAXN];

int n, k;

ll ans;

void dfs(int v, int pr = -1) {    
    for (int i = 0; i <= k; ++i) {
        ans = max(ans, dp[0][i][v]);
        ans = max(ans, dp[1][i][v]);
    } 

    for (int to : adj[v]) {
        if (to != pr) {
            for (int i = 0; i <= k; ++i) {
                dp[0][i][to] = max(dp[0][i][v], dp[1][i][v]);
                dp[1][i + 1][to] = max(dp[0][i][v], dp[1][i][v]) + neigh[to] - arr[v];
            }

            dfs(to, v);
        }
    }
}

void solve() {
    scanf("%d %d", &n, &k);

    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);
        neigh[u] += arr[v];
        neigh[v] += arr[u];
        adj[u].pb(v);
        adj[v].pb(u);
    }    

    vector<int> vs;

    if (n <= 1000) {
        for (int i = 1; i <= n; ++i) {
            vs.pb(i);
        }
    }
    else {
        vs.pb(1);
    }

    for (int v : vs) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= k; ++j) {
                dp[0][j][i] = -INF;
                dp[1][j][i] = -INF;
            }
        }

        dp[0][0][v] = 0;
        dp[1][1][v] = neigh[v];
        dfs(v, -1);
    }

    printf("%lld\n", ans);
}

int main() {
    int tt = 1;

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

    return 0;
}

Compilation message

chase.cpp: In function 'void solve()':
chase.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
chase.cpp:67: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 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2660 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2660 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 1148 ms 5524 KB Output is correct
8 Correct 41 ms 2944 KB Output is correct
9 Correct 34 ms 2968 KB Output is correct
10 Correct 1258 ms 5504 KB Output is correct
11 Correct 392 ms 3632 KB Output is correct
12 Correct 84 ms 3072 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 170200 KB Output is correct
2 Correct 712 ms 169036 KB Output is correct
3 Correct 542 ms 166392 KB Output is correct
4 Correct 85 ms 11060 KB Output is correct
5 Correct 872 ms 164500 KB Output is correct
6 Correct 859 ms 166044 KB Output is correct
7 Correct 857 ms 166092 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2660 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 1148 ms 5524 KB Output is correct
8 Correct 41 ms 2944 KB Output is correct
9 Correct 34 ms 2968 KB Output is correct
10 Correct 1258 ms 5504 KB Output is correct
11 Correct 392 ms 3632 KB Output is correct
12 Correct 84 ms 3072 KB Output is correct
13 Correct 710 ms 170200 KB Output is correct
14 Correct 712 ms 169036 KB Output is correct
15 Correct 542 ms 166392 KB Output is correct
16 Correct 85 ms 11060 KB Output is correct
17 Correct 872 ms 164500 KB Output is correct
18 Correct 859 ms 166044 KB Output is correct
19 Correct 857 ms 166092 KB Output is correct
20 Incorrect 861 ms 168180 KB Output isn't correct
21 Halted 0 ms 0 KB -