oj.uz

Submission #57887

# Submission time Handle Problem Language Result Execution time Memory
57887 2018-07-16T13:31:10 Z gabrielsimoes Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 252972 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e5+10, MAXV = 101;

int n, vMax;
ll p[MAXN];
vector<int> g[MAXN];
int a[MAXN], b[MAXN];

ll dp[MAXN][MAXV][3];
ll f(int curEdge, int v, int dir) {
    if (v == 0) return 0;

    ll &ret = dp[curEdge][v][dir];
    if (ret != -1) return ret;
    ret = 0;

    int cur, prev;
    if (dir == 0) cur = curEdge, prev = -1;
    else if (dir == 1) prev = a[curEdge], cur = b[curEdge];
    else cur = a[curEdge], prev = b[curEdge];

    ll sumAll = 0;
    for (int edge : g[cur]) {
        int nx = a[edge] == cur ? b[edge] : a[edge];
        if (nx != prev) {
            sumAll += p[nx];
        }
    }

    for (int edge : g[cur]) {
        int nx = a[edge] == cur ? b[edge] : a[edge];
        if (nx != prev) {
            int dir = (cur == a[edge] ? 1 : 2);
            ret = max(ret, max(f(edge, v, dir),
                               f(edge, v-1, dir) + sumAll));
        }
    }

    // printf("dp %-2d %-2d %-2d == %lld\n", curEdge, v, dir, ret);
    // printf("dp: cur %-2d prev %-2d v %-2d == %lld\n", cur, prev, v, ret);
    return ret;
}

int main() {
    memset(dp, -1, sizeof(dp));

    scanf("%d%d", &n, &vMax);
    for (int i = 1; i <= n; i++) scanf("%lld", &p[i]);
    for (int i = 1; i < n; i++) {
        scanf("%d%d", &a[i], &b[i]);
        g[a[i]].push_back(i);
        g[b[i]].push_back(i);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f(i, vMax, 0));
    }

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

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &vMax);
     ~~~~~^~~~~~~~~~~~~~~~~~~
chase.cpp:51:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%lld", &p[i]);
                                  ~~~~~^~~~~~~~~~~~~~~
chase.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 239992 KB Output is correct
2 Correct 178 ms 239992 KB Output is correct
3 Correct 176 ms 239992 KB Output is correct
4 Correct 211 ms 239992 KB Output is correct
5 Correct 173 ms 240032 KB Output is correct
6 Correct 173 ms 240060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 239992 KB Output is correct
2 Correct 178 ms 239992 KB Output is correct
3 Correct 176 ms 239992 KB Output is correct
4 Correct 211 ms 239992 KB Output is correct
5 Correct 173 ms 240032 KB Output is correct
6 Correct 173 ms 240060 KB Output is correct
7 Correct 182 ms 240120 KB Output is correct
8 Correct 175 ms 240244 KB Output is correct
9 Correct 254 ms 240400 KB Output is correct
10 Correct 174 ms 240516 KB Output is correct
11 Correct 175 ms 240516 KB Output is correct
12 Correct 181 ms 240708 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3949 ms 250732 KB Output is correct
2 Correct 3781 ms 252972 KB Output is correct
3 Execution timed out 4050 ms 252972 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 239992 KB Output is correct
2 Correct 178 ms 239992 KB Output is correct
3 Correct 176 ms 239992 KB Output is correct
4 Correct 211 ms 239992 KB Output is correct
5 Correct 173 ms 240032 KB Output is correct
6 Correct 173 ms 240060 KB Output is correct
7 Correct 182 ms 240120 KB Output is correct
8 Correct 175 ms 240244 KB Output is correct
9 Correct 254 ms 240400 KB Output is correct
10 Correct 174 ms 240516 KB Output is correct
11 Correct 175 ms 240516 KB Output is correct
12 Correct 181 ms 240708 KB Output is correct
13 Correct 3949 ms 250732 KB Output is correct
14 Correct 3781 ms 252972 KB Output is correct
15 Execution timed out 4050 ms 252972 KB Time limit exceeded
16 Halted 0 ms 0 KB -