Submission #104952

#	Time	Username	Problem	Language	Result	Execution time	Memory
104952		eriksuenderhauf	Chase (CEOI17_chase)	C++11	100 / 100	500 ms	253048 KiB

chase

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 1; i <= (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
vi adj[MAXN];
ll p[MAXN], dp[2][MAXN][101], ans = 0, sum[MAXN];
int vv;

void dfs(int u, int pa)
{
    ll sm = sum[u] - p[pa];;
    ll m1[101] = {0}, m2[101] = {0};
    dp[0][u][0] = dp[1][u][0] = 0;
    dp[1][u][1] = sm + p[pa];
    for (int v: adj[u]) if (v != pa)
    {
        dfs(v, u);
        for (int i = 1; i <= vv; i++)
        {
            dp[0][u][i] = max(dp[0][u][i], max(dp[0][v][i], dp[0][v][i - 1] + sm));
            dp[1][u][i] = max(dp[1][u][i], max(dp[1][v][i], dp[1][v][i - 1] + sm + p[pa] - p[v]));
            if (dp[0][v][i] >= m1[i])
                m2[i] = m1[i], m1[i] = dp[0][v][i];
            else if (dp[0][v][i] > m2[i])
                m2[i] = dp[0][v][i];
        }
    }
    for (int v: adj[u])
    {
        if (v == pa) continue;
        if (vv > 0) ans = max(ans, sm + p[pa] + dp[0][v][vv - 1]);
        for (int i = 0; i <= vv; i++)
        {
            ll x = max(dp[1][v][i], i == 0 ? 0 : dp[1][v][i - 1] + sm + p[pa] - p[v]);
            if (m1[vv - i] == dp[0][v][vv - i])
                ans = max(ans, x + m2[vv - i]);
            else
                ans = max(ans, x + m1[vv - i]);
        }
    }
}

int main()
{
    int n;
    ni(n), ni(vv);
    nal(p, n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        ni(u), ni(v);
        adj[u].pb(v);
        adj[v].pb(u);
        sum[u] += p[v], sum[v] += p[u];
    }
    dfs(1, 0);
    prl(ans);
    return 0;
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(vv);
          ^
chase.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
chase.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define nl(n) scanf("%lld", &(n))
               ~~~~~^~~~~~~~~~~~~~
chase.cpp:10:50: note: in expansion of macro 'nl'
 #define nal(a, n) for (int i = 1; i <= (n); i++) nl(a[i])
                                                  ^~
chase.cpp:72:5: note: in expansion of macro 'nal'
     nal(p, n);
     ^~~
chase.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(u), ni(v);
              ^
chase.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30