oj.uz

Submission #162245

# Submission time Handle Problem Language Result Execution time Memory
162245 2019-11-07T09:48:45 Z karma Chase (CEOI17_chase) C++14
100 / 100
 697 ms 332124 KB 
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}

const int N = int(1e5) + 3;

int n, k, u, v, c[N], p[N];
ll s[N], res, f[N][101][2], g[N][101][2];
vector<int> a[N];

void DFS(int u) {
    f[u][1][1] = g[u][1][1] = s[u];
    for(int v: a[u]) {
        if(v == p[u]) continue;
        p[v] = u; DFS(v);
        for(int j = 1, t = k - 1; j <= k; ++j, --t) {
           res = max({res, f[v][j][0] + g[u][t][0], f[v][j][1] + g[u][t][0]});
           res = max(res, max(f[v][j][0], f[v][j][1]) + g[u][t][1] - c[v]);
           res = max({res, g[v][j][0] + f[u][t][0], g[v][j][0] + f[u][t][1]});
           res = max(res, g[v][j][1] - c[u] + max(f[u][t][0], f[u][t][1]));
        }
        for(int j = 1; j <= k; ++j) {
           f[u][j][0] = max({f[u][j][0], f[v][j][0], f[v][j][1]});
           f[u][j][1] = max(f[u][j][1], max(f[v][j - 1][0], f[v][j - 1][1]) + s[u] - c[v]);
           g[u][j][0] = max({g[u][j][0], g[v][j][0], g[v][j][1] - c[u]});
           g[u][j][1] = max(g[u][j][1], max(g[v][j - 1][0], g[v][j - 1][1] - c[u]) + s[u]);
           res = max({res, g[u][j][1], f[u][j][1]});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "chase"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    Cin(n, k);
    for(int i = 1; i <= n; ++i) Cin(c[i]);
    for(int i = 1; i < n; ++i) {
        Cin(u, v);
        a[u].pb(v), a[v].pb(u);
        s[u] += c[v], s[v] += c[u];
    }
    DFS(1);
    cout << res;
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory 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 2808 KB Output is correct
5 Correct 4 ms 2808 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 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 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 9 ms 6008 KB Output is correct
8 Correct 7 ms 6008 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 558 ms 331984 KB Output is correct
2 Correct 550 ms 332024 KB Output is correct
3 Correct 564 ms 326324 KB Output is correct
4 Correct 361 ms 325912 KB Output is correct
5 Correct 566 ms 325856 KB Output is correct
6 Correct 553 ms 325952 KB Output is correct
7 Correct 556 ms 325880 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory 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 2808 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 9 ms 6008 KB Output is correct
8 Correct 7 ms 6008 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 558 ms 331984 KB Output is correct
14 Correct 550 ms 332024 KB Output is correct
15 Correct 564 ms 326324 KB Output is correct
16 Correct 361 ms 325912 KB Output is correct
17 Correct 566 ms 325856 KB Output is correct
18 Correct 553 ms 325952 KB Output is correct
19 Correct 556 ms 325880 KB Output is correct
20 Correct 547 ms 325880 KB Output is correct
21 Correct 332 ms 326008 KB Output is correct
22 Correct 551 ms 325900 KB Output is correct
23 Correct 352 ms 325908 KB Output is correct
24 Correct 556 ms 325740 KB Output is correct
25 Correct 697 ms 325832 KB Output is correct
26 Correct 517 ms 332124 KB Output is correct
27 Correct 513 ms 332068 KB Output is correct